そのうち誰かの役に立つ

もしくは誰の役にも立たない

AtCoderチャレンジ供養会場(2020/05/22-2020/05/28)

コンテストでの時間切れや解けなかった過去問を振り返って供養していく

5/22: AtCoder Regular Contest 050 D - Suffix Concat

供養

問題

Difficulty: 2405(estimated) (記事作成時点)

解法

  • 任意の  i, j について  p_{i} \le p_{j} \iff S_{i}S_{j} \le S_{j}S_{i} であるという関係が成り立つように  1 \dots N をソートする
  •  S_{i}Suffix Arrayでの位置  \mathit{rank}(i) および任意の  S_{i}, S_{j} 間の最長共通接頭辞  \mathit{LCP}(i, j) を求められれば、上記の関係は以下のように表せる
    •  \mathit{LCP}(i, j) \lt N + 1 - \mathrm{max}(i, j) であるならば  S_{i}S_{j} および  S_{j}S_{i} の最長共通接頭辞もそれぞれ先頭の  S_{i}, S_{j} 部分までしかないので、 S_{i}S_{j} S_{j}S_{i} の関係は  \mathit{rank}(i) \mathit{rank}(j) の関係に等しい
    • 上記以外のとき、先頭から  |S_{i}| 文字を比較して残った部分は  S_{\mathrm{min}(i, j)} および  S_{N + 1 - |j - i|} となり、上記と同様これは  \mathit{rank}(\mathrm{min}(i, j)) \mathit{rank}(N + 1 - |j - i|) に等しい
  •  \mathit{rank}(i) を計算時間  O(N)で構築する方法(SA-IS algorithm)および  \mathit{LCP}(i, j) を前処置  O(N\mathrm{log}N)、クエリ  O(1) で計算する方法(SparseTableを用いたKasai algorithm)などがあるので、それらを用いて計算する

実装は

  1.  S からSuffix Array  \mathit{SA} を構築する
    • [\mathit{SA}] は末尾の空文字を含んだ長さ  N + 1 の配列とする
  2. 長さ  N + 1 の配列  R を用意し、 0 \le i \le N について  \mathit{rank}(\mathit{SA}_{i}) = i とする
  3.  i, j を入力とし、 S_{i} S_{j} の最長共通接頭辞の長さを返す関数  \mathit{LCP}(i, j) を用意する
  4. 下記のルールで  A = 0, \dots, N - 1 をソートする
    •  \mathit{LCP}(i, j) \lt N - \mathrm{max}(i, j) のとき、 i, j の大小関係は  \mathit{rank}(i), \mathit{rank}(j) の大小関係に等しい
    • 上記以外の場合は  \mathit{rank}(\mathrm{min}(i, j)) \lt \mathit{rank}(N - |j - i|)\; \mathrm{XOR}\; i \lt j となる
  5.  0 \le i \lt N について  A_{i} を出力していく

計算量は  O(N\mathrm{log}N)

公式解説

躓いた点

  • 解法に使用したアルゴリズムやデータ構造(SA-IS, Kasai, SparseTable)をいずれも実装したことが無かった

5/23: AtCoder Grand Contest 044 A - Pay to Win

供養

問題

Difficulty: 1432 (記事作成時点)

解法

  •  (N, 0) から始めて  (0, C) にすることを考える
  •  (n, c) を見ているとき、 n を減らす方法は以下が考えられる
    •  k - n \% k 増加させてから  k で割って  \lceil \frac{n}{k} \rceil にする
      • これで到達する状態は  (\lceil \frac{n}{k} \rceil, c + (k - n \% k) \times D + X_{k})
      •  k \in \lbrace 2, 3, 5 \rbrace X_{k} k に対応する  A, B, C のいずれか
    •  n \% k 減少させてから  k で割って  \lfloor \frac{n}{k} \rfloor にする
      • これで到達する状態は  (\lfloor \frac{n}{k} \rfloor, c + (n \% k) \times D + X_{k})
    • 愚直に1ずつ減少させる
      • これで到達する状態は  (n - d, c + d \times D)
  • 1つ目もしくは2つ目の手段で到達可能な  n \lceil \frac{N}{2^{a}3^{b}5^{c}} \rceil, \lfloor \frac{N}{2^{a}3^{b}5^{c}} \rfloor で表せる
    •  N \le 10^{18} より  0 \le a \le 60, 0 \le b \le 38, 0 \le c \le 26 程度の領域に収まる
    • これらすべてを状態に持つと約13,000通り程度、 k で割る前の  kn を含めても  5 \times 10^{4} 程度の状態数に収まる
  • 連想配列などで動的に状態を作りながら探索して  (0, C) を求める

実装は

  1. 配列  X を用意し、 X_{2} = A, X_{3} = B, X_{5} = C とする
  2. 連想配列  M を用意し、 M_{N} = 0 とする
  3. Priority Queue  Q を用意する
    •  \mathit{pop}() Q の各エントリの第2要素が最小のエントリを返す
  4.  (N, 0) Q にpushする
  5.  Q が空になるまで以下を繰り返す
    •  Q から popして  (n, c) とする
    •  M_{n} \lt c ならば何もせず次に行く
    •  k = 2, 3, 5 について下記の操作を実施する
      •  a = n \% k とする
      •  a = 0 のとき、以下の操作を実施する
        •  c^{'} = c + X_{k} とする
        •  n - \frac{n}{k} \lt 10^{9} ならば  c^{'} = \mathrm{min}(c + (n - \frac{n}{k}) \times D, c^{'}) とする
        •  M_{\frac{n}{k}} が未定義もしくは  c^{'} \lt M_{\frac{n}{k}} ならば、 M_{\frac{n}{k}} = c^{'} とし  (\frac{n}{k}, c^{'}) Q にpushする
      •  a \gt 0 のとき、以下の操作を実施する
        •  c^{'} = c + (k - a) \times D とする
        •  M_{n + k - a} が未定義もしくは  c^{'} \lt M_{n + k - a} ならば、 M_{n + k - a} = c^{'} とし  (n + k - a, c^{'}) Q にpushする
        •  c^{'} = c + a \times D とする
        •  M_{n - a} が未定義もしくは  c^{'} \lt M_{n - a} ならば、 M_{n - a} = c^{'} とし  (n - a, c^{'}) Q にpushする
  6.  M_{0} を出力する
  7. 上記の方法で  T 問解く

計算量は  O(T(\mathrm{log}N)^{4})

公式解説

躓いた点

  • コンテスト中は  0 \to N まで構成する方法を考えて失敗した

5/24: AtCoder Grand Contest 044 B - Joker

供養

問題

Difficulty: 1925 (記事作成時点)

解法

  •  H_{k, p} で、今までに  k 人が席を立った状態の時に  p が席を立った場合、何人からヘイトを集めるかを表すとする
    • 実際に  k + 1 人目に席を立つかは無視する
  • 0-indexedで  p は前から  i = \lfloor \frac{p}{N} \rfloor 番目、左から  j = p \% N 番目に座っているので、  H_{0, p} = \mathrm{min}(i, j, N - 1 - i, N - 1 , j) で求められる
  •  H_{k - 1, p} から  H_{k, p} に更新するとき、 k 番目に席を立った  p_{k} から前後左右に探索していく
    •  i を見ているとき、 i の各隣  j について  H_{k - 1, i} + s_{k, i} \lt H_{k - 1, j} ならば  j を探索リストに追加する
      •  s_{k, i} k 番目までに  i が席を立っていれば0、そうでなければ1
  •  p_{1}, \dots, p_{N^{2}} まで更新をしながら合計を求める

実装は

  1.  (N + 2) \times (N + 2) の配列  H, S を用意する
  2.  0 \le i \lt N, 0 \le j \lt N について、 H_{i + 1, j + 1} = \mathrm{min}(i, j, N - 1 - i, N - 1 - j), S_{i + 1, j + 1} = 1 とする
  3.  C = 0 とする
  4. 配列  Q を用意する
  5.  0 \le i \lt N^{2} について以下の操作を実施する
    •  p = p_{i} - 1 とし、 x = \lfloor \frac{p}{N} \rfloor, y = p \% N とする
    •  C = C + H_{x, y}, S_{x, y} = 0 とする
    •  p Q の末尾に挿入する
    •  Q が空になるまで以下の操作を実行する
      •  Q の先頭要素を取り出し  q とする
      •  x = \lfloor \frac{q}{N} \rfloor, y = q \% N とする
      •  c = H_{x, y} + S_{x, y} とする
      •  c \lt H_{x - 1, y} ならば、 H_{x - 1, y} = c とし  p - N Q の末尾に追加する
      •  c \lt H_{x + 1, y} ならば、 H_{x + 1, y} = c とし  p + N Q の末尾に追加する
      •  c \lt H_{x, y - 1} ならば、 H_{x, y - 1} = c とし  p - 1 Q の末尾に追加する
      •  c \lt H_{x, y + 1} ならば、 H_{x, y + 1} = c とし  p + 1 Q の末尾に追加する
  6.  C を出力する

計算量は  H_{k, p} が減るところが探索されることから  O(\sum_{p}H_{0, p}) = O(N^{3})

公式解説

躓いた点

  •  H_{k, p} の更新に手こずった

5/25: AtCoder Grand Contest 038 C - LCMs

供養

問題

Difficulty: 2410 (記事作成時点)

解法

  •  V = \mathrm{max}(A_{i}) とする
  •  \sum_{d | k}w_{d} = k^{-1} であるような数列  w_1, \dots, w_{V} を考える
    •  d | k d k の約数であることを意味する
    •  w_{k} = k^{-1} - \sum_{d | k \land d \lt k}w_{d} なので、以下のように構築できる
      •  w_{k} = k^{-1} とする
      •  k = 1, \dots および  m = 2, \dots について、 w_{mk} から  w_{k} を減算する
  •  \mathit{lcm}(x, y) = \frac{xy}{\mathit{gcd}(x, y)} = xy\sum_{d | \mathit{gcd}(x, y)}w_d = xy\sum_{d | x \land d | y}w_d と展開できる
  • 上記より、 \sum_{i = 0}^{N - 2}\sum_{j = i + 1}^{N - 1}\mathit{lcm}(A_{i}, A_{j}) = \sum_{i = 0}^{N - 2}\sum_{j = i + 1}^{N - 1}\bigl(A_{i}A_{j}\sum_{d | A_{i} \land d | A_{j}}w_{d}\bigr) となり、これを  d を軸に書くと  \sum_{d = 1}^{V}\bigl(w_{d}\sum_{d | A_{i} \land d | A_{j} \land i \lt j}A_{i}A_{j}\bigr) である
  • さらに  \sum_{d | A_{i} \land d | A_{j} \land i \lt j}A_{i}A_{j} = \frac{\bigl( \sum_{d | A_{i}}A_{i}\bigr)^{2} - \sum_{d | A_{i}}A_{i}^{2}}{2} より、 \sum_{d = 1}^{V}\frac{w_{d}}{2}\bigl( \sum_{d | A_{i}}A_{i}\bigr)^{2} - \sum_{d = 1}^{V}\frac{w_{d}}{2}\sum_{d | A_{i}}A_{i}^{2}、第2項について  i を軸に戻すと  \sum_{i = 0}^{N - 1}A_{i}^{2}\sum_{d | A_{i}}\frac{w_{d}}{2} = \frac{1}{2}\sum_{i = 0}^{N - 1}\frac{A_{i}^{2}}{A_{i}} = \frac{1}{2}\sum_{i = 0}^{N - 1}A_{i} となる
  • したがって、 \frac{1}{2}\Bigl( \sum_{d = 1}^{V}w_{d}\bigl( \sum_{d | A_{i}}A_{i}\bigr)^{2} - \sum_{i = 0}^{N - 1}A_{i} \Bigr) を求める
  •  \sum_{d | A_{i}}A_{i} の部分は、 1 \le x \le V について  x = A_{i} であるような  A_{i} の数  C_{x} を前計算しておくと、 \sum_{k = 1}^{\lfloor \frac{V}{d} \rfloor}kdC_{kd} となり、この部分の計算量は  O(\sum_{d = 1}^{V}\frac{V}{d}) = O(V\mathrm{log}V) になる

実装は

  1.  V = \mathrm{max}(A_{i}) とする
  2.  1 \le k \le V について  I_{k} = k^{-1} となるよう配列  I を作る
  3. 長さ  V + 1 の配列  W を用意し、 1 \le v \le V について以下の処理を実施する
    •  W_{v} I_{v} を加算する
    •  2 \le k \le \lfloor \frac{V}{v} \rfloor について  W_{kv} から  W_{v} を減算する
  4.  S = 0 とする
  5. 長さ  V + 1 の配列  C を用意し、 0 \le i \lt N について以下の処理を実施する
    •  C_{A_{i}} A_{i} を加算する
    •  S から  A_{i} を減算する
  6.  1 \le d \le V について以下の処理を実施する
    •  x = 0 とする
    •  1 \le k \le \lfloor \frac{V}{d} \rfloor について、 x C_{kd} を加算する
    •  S W_{d} \times x \times x を加算する
  7.  S \times I_{2} を出力する

計算量は  V = \mathrm{max}(A_{i}) として  O(N + V\mathrm{log}V)

公式解説

躓いた点

  • GCDを数列の和で表現する発想は無かった
  • 高速化のための式展開に苦戦した

5/26: AtCoder Regular Contest 027 D - ぴょんぴょんトレーニン

供養

問題

Difficulty: 2410(estimated) (記事作成時点)

解法

  •  1, \dots, N M = \mathrm{max}(\lceil \sqrt{N} \rceil, 10) ごとに分割して区間ごとに考える
    • 以降の計算で長さ10 i.e.  h_{i} の最大値のベクトルを入出力に用いるため  M の最低値をboundしている
  •  s, t が同じ区間にあるときは愚直に計算する
  •  s, t が異なる区間にあるとき、必要な計算は以下の3種類に分けられる
    •  F_{1}(s):  (a - 1)M \lt s \le aM である区間  a で、 s を入力に区間  a +  1 に渡すためのベクトル  V = (v_{1}, \dots, v_{10}) を作る
      •  V aM + 1, \dots, aM + 10 に入力される初期値となる
    •  F_{2}(V, b):  s \le (b - 1)M \land bM \lt t である区間  b で、ベクトル  V を入力に区間  b + 1 に渡すためのベクトル  W = (w_{1}, \dots, w_{10}) を作る
      • この区間は存在しない可能性がある
    •  F_{3}(V, t):  (c - 1)M \lt t \le cM である区間  c で、ベクトル  V を入力にクエリの回答を計算する
  •  F_{1} について前計算しておくと、 F_{2}(V, b) = v_{1} \times F_{1}( (b - 1)M + 1) + \dots + v_{10} \times F_{1}( (b - 1)M + 10) で計算できる

実装は

  1.  M = 10 とし、 M \times M \lt N である間  M をインクリメントする
  2. 以下の関数  F_{0}(s, t) を作成する
    • 長さ  M の配列  A を用意する
    •  m = \lfloor \frac{s}{M} \rfloor \times M とし、 A_{s - m} をインクリメントする
    •  i = s - m, \dots, t - m について以下の処理を実施する
      •  i \lt j \le \mathrm{min}(i + h_{i + m}, t - m) について、 A_{j} A_{i} を加算する
    •  A_{t - m} を返す
  3.  N \times 10 の配列  U を用意する
  4.  i = \lfloor \frac{N}{M} \rfloor \times M - 1, \dots, 0 について、以下の計算を実施する
    •  m = (\lfloor \frac{i}{M} \rfloor + 1) \times M とする
    •  i \lt j \le i + h_{i} について、以下の処理を実施する
      •  j \ge m ならば、 U_{i, j -m} をインクリメントする
      •  j \lt m ならば、 0 \le k \lt 10 について  U_{i, k} U_{j, k} を加算する
  5. 以下の関数  F_{2}(V, b) を用意する
    • 長さ10の配列  W を用意する
    •  0 \le i \lt 10, 0 \le j \lt 10 について、 v_{i} \times U_{i + bM, j} W_{j} に加算する
    •  W を返す
  6. 以下の関数  F_{3}(V, t) を用意する
    • 長さ  M の配列  A を用意し、 0 \le i \lt 10 について  A_{i} = V_{i} とする
    •  m = \lfloor \frac{t}{M} \rfloor \times M とする
    •  i = 0, \dots, t - m, i \lt j \le \mathrm{min}(i + h_{i + m}, t - m) について、 A_{j} A_{i} を加算する
    •  A_{t - m} を出力する
  7.  0 \le d \lt D について、以下の処理を実施する
    •  s_{d}, t_{d} をそれぞれデクリメントする
    •  a = \lfloor \frac{a_{d}}{M} \rfloor, c = \lfloor \frac{t_{d}}{M} \rfloor とする
    •  a = c ならば  F_{0}(s_{d}, t_{d}) を出力する
    •  a \ne c ならば以下の処理を実施する
      •  V = U_{s_{d}} とする
      •  b = a + 1, \dots, c - 1 について  V = F_{2}(V, b) と更新していく
      •  F_{3}(V, t_{d}) を出力する

計算量は前処理が  O(N) F_{0}, F_{3} がそれぞれ  O(M) = O(\sqrt{N}) F_{2} O(1) でクエリごとに最大  O(\sqrt{N}) 回呼び出されるので、クエリ全体で  O(\sqrt{N})、全体で  O(D\sqrt{N})

公式解説

躓いた点

  • ベクトルで渡す発想が出ず平方分割できなかった
  • 実装バグでWA

5/27: AtCoder Regular Contest 092 E - Both Sides Merger

供養

問題

Difficulty: 2411(estimated) (記事作成時点)

解法

  •  \mathrm{max}(A_{i}) \le 0 のときは最大値の要素1つだけ残すのが最適戦略となる
  • 最終的に残る要素が  \sum_{i \in R}A_{i} としたとき、 R は偶数のみもしくは奇数のみからなる
    • 与えられた操作で偶数番目の要素と奇数番目の要素を残すことは不可能
  • 残す要素の偶奇  m \in \lbrace 0, 1 \rbrace を決めたとき、以下の方法で最大値を取ることができる
    •  i = N, \dots, 1 について、 i \% 2 = m \land A_{i} \le 0 ならば  i を取り除く
      • 逆順に取り除けば次に見る要素の位置に影響を及ぼさない
    •  m = 0 \lor A_{1} \le 0 ならば  1 を取り除く
      • この時点で残った要素の先頭が残す要素になるようにする
    • この時点での偶数番目の要素を全て取り除く
      • この時点での残った要素数  N^{'} を数えておけば  \lfloor \frac{N^{'}}{2} \rfloor 2 を取り除けばよい
  • 残った要素の値は  \mathrm{max}(\sum_{i \% 2 = 0 \land A_{i} \gt 0}A_{i}, \sum_{i \% 2 = 1 \land A_{i} \gt 0}A_{i})

実装は

  1. 配列  S を用意する
  2.  \mathrm{max}(A) \le 0 のとき、以下の処理を実施する
    •  i = N - 1 とし、 A_{i} = \mathrm{max}(A) となるまで以下の操作を繰り返す
      •  i + 1 S の末尾に追加する
      •  i = i - 1 とする
    • 1 S の末尾に  i 回追加する
    •  \mathrm{max}(A) を出力する
    •  N - 1 を出力する
    •  S の要素を先頭から出力していって終了
  3. 以下の関数  F(k) を用意する
    •  i = k, k - 2, \dots, k \% 2 について、以下の操作を実施する
      •  A_{i} \gt 0 ならば何もせず次に行く
      •  i + 1 S の末尾に追加する
      •  i = 0 \lor i = N - 1 ならば  N = N - 1 とし、そうでなければ  N = N - 2 とする
    •  k \% 2 \ne 0 \lor A_{0} \le 0 ならば  1 S の末尾に追加し、 N = N - 1 とする
  4.  O = \sum_{i \% 2 = 0 \land A_{i} \gt 0}A_{i}, E = \sum_{i \% 2 = 1 \land A_{i} \gt 0}A_{i} とする
  5.  O \ge E ならば  F(\lfloor \frac{N - 1}{2} \rfloor \times 2)、そうでなければ  F(\lfloor \frac{N}{2} \rfloor \times 2 - 1) を実行する
  6.  2 S の末尾に  \lfloor \frac{N}{2} \rfloor 回追加する
  7.  \mathrm{max}(O, E) を出力する
  8.  S の長さを出力する
  9.  S の各要素を先頭から出力していく

計算量は  O(N)

公式解説

躓いた点

  • 実装のバグを多数埋めてWA

5/28: AtCoder Grand Contest 039 C - Division by Two with Something

供養

問題

Difficulty: 2428 (記事作成時点)

解法

  • 操作を1回すると右シフトして押し出されたbitを反転して最上位にセットすることになる
  • したがって、 2N 回操作すれば1回以上は元の状態が現れる
  • bit列  S k \lt 2N 回の操作で元の状態が現れるときの条件は
    •  2N \% k = 0 かつ  \frac{2N}{k} は奇数である
      •  \frac{2N}{k} が偶数の場合、 N 回の操作でも元の状態が現れることになるが、そのときは  S をbit反転した状態なので矛盾が生じる
    •  S の先頭  \frac{k}{2} bit を  T T のbit反転を  T^{-1} とすると、 S = TT^{-1}T \dots T^{-1}T となっている
  •  k = 1, \dots, \lfloor \frac{N}{3} \rfloor について、 N \% 2k = k であれば  2k 回の操作で元に戻るbit列を作れる可能性がある
    • そのような数列を昇順に  k_{1}, \dots, k_{m} とする
  •  2k_{i} 回の操作で元に戻る  X 以下のbit列は、 X の先頭  k_{i} bitで表される数  X_{k_{i}} について、  T = 0, \dots, X_{k_{i}} - 1 で構成される  S であれば確実に  S \lt X となる
    •  T = X_{k_{i}} のときは、それで  S を構成して  S \le X か確かめる
  •  k_{i} \% k_{j} = 0 である  k_{j} \lt k_{i} について、 2k_{j} 回の操作で元に戻るbit列は  2k_{i} 回の操作で戻るbit列としてもカウントされているので、その分を引いて数える

実装は

  1.  X の上位  n bitからなる数を返す関数を  F(n) とする
  2.  A = 2N(F(N) + 1) とする
  3. 配列  D を用意する
  4.  k = 1, \dots, \lfloor \frac{N}{3} \rfloor について、 N \% 2k = k ならば  k D の末尾に追加する
  5.  D と同じ長さの配列  C を用意する
  6.  0 \le i \lt |D| について、以下の処理を実施する
    •  C_{i} = F(D_{i}) とする
    • 長さ  N の配列  Y を用意し、 Y_{i} = X_{i \% D_{i}} \oplus (\lfloor \frac{i}{D_{i}} \rfloor \% 2) とする
    •  Y \le X ならば  C_{i} をインクリメントする
    •  0 \le j \lt i について、 D_{i} \% D_{j} = 0 ならば  C_{i} から  C_{j} を減算する
    •  A から  2C_{i}(N - D_{i}) を減算する
  7.  A を出力する

計算量は  O(N|D|^{2})

公式解説

躓いた点

  • 包除原理の部分を上手く実装できなかった