torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

AtCoder Beginner Contest 345, C : One Time Swap

問題概要

 文字列 $S$ が与えられる.$S$ に対し,$S$ の添字 $i, j$ ($1 \leq i < j \leq |S|$) を選び,$S_i$ と $S_j$ を入れ替える操作をちょうど $1$ 回行う.この操作によって作られる文字列は何種類あるか?

制約

  • $1 \leq |S| \leq 10^6$
  • $S_i \in \mathcal C$

 ここで,$\mathcal C$ はすべての英小文字からなる集合とする.

続きを読む

AtCoder Beginner Contest 345, D : Tiling

問題概要

 $1 \times 1$ のセルからなる $h \times w$ のグリッド状の盤面と $n$ 枚のタイルがあり,タイル $i$ は $A_i \times B_i$ の長方形状である.
 各タイルについて,グリッドに沿い,かつ盤面からはみ出さない範囲で自由に位置と向きを決めてグリッドに配位することができる(配置しなくてもよい).
 グリッドのすべてのセルがちょうど $1$ 枚のタイルに被覆されている状態にできるか?

制約

  • $1 \leq n \leq 7$
  • $1 \leq h, w \leq 10$
  • $1 \leq A_i, B_i \leq 10$
続きを読む

AtCoder Beginner Contest 344, D : String Bags

問題概要

 文字列の列が $n$ 個与えられる.$i$ ($1 \leq i \leq n$) 番目の列は $S_i = \langle S_{ i, 1 }, S_{ i, 2 }, \dots, S_{ i, A_i } \rangle$ である.
 ここで,次の処理を行う.

  1. 変数 $S$ を用意し,$S \leftarrow \epsilon$ とする*1
  2. $i = 1, 2, \dots, n$ について,順に次の処理を行う.
    1. 次の 2 つの内,いずれかを行う.
      1. 次の処理を行う.
        1. 整数 $j$ ($1 \leq j \leq A_i$) を選ぶ.
        2. $S \leftarrow S + S_{ i, j }$ とする.
      2. 何もしない.

 操作終了後の $S$ を与えられる文字列 $T$ に一致させるとき,$S$ に代入する操作の回数の最小値はいくらか? 不可能な場合はそのことを報告せよ.

制約

  • $1 \leq n, |T| \leq 100$
  • $1 \leq A_i, | S_{ i, j } | \leq 10$

*1:ここで,$\epsilon$ は空文字列を表す.

続きを読む

AtCoder Beginner Contest 344, E : Insert or Erase

問題概要

 相異なる $n$ 項からなる数列 $A = \langle A_1, A_2, \dots, A_n \rangle$ がある.
 次の 2 種からなるクエリを $q$ 個,順に処理せよ.

  • $( 1, x, y )$ : $A$ に含まれる $x$ の直後に $y$ を挿入する($x$ の存在は保証される).
  • $( 2, x )$ : $A$ に含まれる $x$ を削除する($x$ の存在は保証される).

各クエリの処理後,$A$ は空でなく,要素は相異なる.
 最終的な $A$ を出力せよ.

制約

  • $1 \leq n, q \leq 2 \times 10^5$
  • $1 \leq A_i \leq 10^9$
続きを読む

AtCoder Beginner Contest 342, E : Last Train

問題概要

 $1$ から $n$ で番号付けられた $n$ 個の駅があり,$m $ 種類の路線が運行されている.各路線は 6 個の整数 $l, d, k, c, a, b$ *1で説明され,その意味は,

  • 駅 $u$ から駅 $v$ へ向かう路線は,
  • 始発が時刻 $l$ であり,
  • $d$ 分間隔で出発し,
  • $k$ 本運行され,
  • $c$ 分で目的地に到着する.

である.
 駅 $s$ から駅 $n$ に到達できる時刻の内最遅のものを $f( s )$ で表す.到達できない場合は $-\infty$ と定義する.
 $f( 1 ), f( 2 ), \dots, f( n - 1 )$ を求めよ.

制約

  • $2 \leq n \leq 2 \times 10^5$
  • $1 \leq m \leq 2 \times 10^5$
  • $1 \leq l, d, k, c \leq 10^9$

*1:書くのが面倒だったので端折っていますが,正確には添字が付きます.原文参照のこと.

続きを読む