そのうち誰かの役に立つ

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

AtCoderチャレンジ供養会場(2020/03/15-2020/03/21)

競技プログラミング AtCoder Priority Queue 期待値計算 DP

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

3/15: パナソニックプログラミングコンテスト2020 E - Three Substrings

供養

問題

Difficulty: 2366 (記事作成時点)

解法

  • a を固定したときに b, c の相対的な開始位置を s_{a, b}, s_{a, c} としたとき、矛盾なく文字列が作れるかを \mathit{AB}_{s_{a, b}}, \mathit{AC}_{s_{a, c}} とする
  • b を固定したときに c の相対的な開始位置を s_{b, c} としたとき、矛盾なく文字列が作れるかを \mathit{BC}_{s_{b, c}} とする
  • s_{a, b} = i, s_{a, c} = j のとき s_{b, c} = j - i となる
  • \mathit{AB}_{s_{a, b}} \land \mathit{AC}_{s_{a, c}} \land \mathit{BC}_{s_{a, c} - s_{a, b}} が \mathrm{true} となる s_{a, b}, s_{a, c} について、最小となる \mathrm{max}(|a|, s_{a, b} + |b|, s_{a, c} + |c|) - \mathrm{min}(0, s_{a, b}, s_{a, c}) が答えとなる

実装は

  1. N = 2000 とする
  2. 2つの文字列 x, y の相対位置とその時に矛盾が無いかを求める関数 F(x, y) を以下のように作る
    • 長さ 5N の ? で構成された文字列 M を作る
    • 0 \le i \lt |x| について M_{2N + i} = x_{i} とする
    • 0 \le i \lt 4N について、下記のように R_{i} を求める
      • 0 \le j \lt |y| について M_{i + j} = y_{j} ならば \mathrm{true}、そうでなければ \mathrm{false}
    • R を返す
  3. \mathit{AB} = F(a, b), \mathit{AC} = F(a, c), \mathit{BC} = F(b, c) とする
  4. n = |a| + |b| + |c| とする
  5. 0 \le i \lt 4N, 0 \le j \lt 4N について \mathit{AB}_{i} \land \mathit{AC}_{j} \land \mathit{BC}_{j - i + 2N} であるとき、 n = \mathrm{min}(\mathrm{max}(|a|, i + |b|, j + |c|) - \mathrm{min}(0, i, j), n) と更新していく
    • -2N \le j - i + 2N \lt 6N になりうるので、 |j - i| \ge 2N ならスキップするなどの工夫が必要
  6. n を出力する

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

公式解説

躓いた点

3/16: AtCoder Regular Contest 091 F - Strange Nim

供養

問題

Difficulty: 2383 (記事作成時点)

解法

  • 任意の山 i について、現在の山の大きさを N、 K_{i} = K とすると、Grundy数 G(N, K) は N \% K = 0 のとき G(N, K) = \frac{N}{K}、 N \% K \ne 0 のとき G(N, K) = G(N - \lfloor \frac{N}{K} \rfloor - 1, K) となる
    • N についての帰納法で証明可能
    • N = 0 のとき、 G(N, K) = 0 である
    • N = n - 1 のとき成立すると仮定して、 N = n を考える
      • Grundy数の定義より G(n, K) \ne G(n - 1, K) \ne \dots \ne G(n - \lfloor \frac{n}{K} \rfloor, K) であり、また G(n, K) \le \lfloor \frac{n}{K} \rfloor である
      • n \% K = 0 のとき、 \lfloor \frac{n - 1}{K} \rfloor = \lfloor \frac{n}{K} \rfloor - 1 より G(n - 1 - \lfloor \frac{n - 1}{K} \rfloor, K) = G(n - \lfloor \frac{n}{K} \rfloor, K) である
        • G(n - 1, K), \dots, G(n - \lfloor \frac{n}{K} \rfloor, K) は 0, \dots, \lfloor \frac{n - 1}{K} \rfloor = \frac{n}{K} - 1 が互いに異なるように1つずつ割り当てられているので、 G(n, K) = \frac{n}{K} となる
      • n \% K \ne 0 のとき、 \lfloor \frac{n - 1}{K} \rfloor = \lfloor \frac{n}{K} \rfloorである
        • G(n - 1, K), \dots, G(n - 1 - \lfloor \frac{n - 1}{K} \rfloor, K) は 0, \dots, \lfloor \frac{n - 1}{K} \rfloor = \lfloor \frac{n}{K} \rfloor が互いに異なるように1つずつ割り当てられているので、 G(n, K) は G(n - 1, K), \dots, G(n - 1 - \lfloor \frac{n}{K} \rfloor, K) に含まれ G(n - 1, K), \dots, G(n - \lfloor \frac{n}{K} \rfloor, K) に含まれない数、すなわち G(n - \lfloor \frac{n}{K} - 1 \rfloor, K) である
  • n \propto K のときの再帰1回あたりの減少量が高々定数なので、愚直に書くと \Omega(K) となる
    • 再帰後の減少量が等しい場合はまとめて減少させる
    • n \% K \ne 0 のとき、 x = \lceil \frac{n \% K}{\lfloor \frac{n}{K} \rfloor + 1} \rceil として G(n, K) = G(n - x \times (\lfloor \frac{n}{K} \rfloor + 1), K) とする
      • 1回の再帰で必ず減少量が1以上小さくなるので、再帰回数は \frac{n}{K} 以下になる
    • n \gt K^{2} のときは1回の再帰で \frac{K - 1}{K} 倍以下になることから、 K 回の再帰で約 e^{-1} 倍以下になる
      • n \le K^{2} となるまでの再帰回数を m 回としたとき n ^{\frac{m}{K}} \le K^{2} より、 m = K\mathrm{log}\frac{n}{K^{2}} となる
      • 1 \le K \le \sqrt{n} の範囲において、 K = \sqrt{\frac{n}{e}} のときに最大値 K をとるので、 n \gt K^{2} の範囲の再帰回数は O(K) である
    • \frac{n}{K} + K は K = \sqrt(n) のときに最大値 \sqrt{n} をとるので、計算量は O(\sqrt(A_{i})) まで落ちる

実装は

  1. n, k が与えられたときにGrundy数を求める関数 G(n, k) を下記のように作成する
    • n \% k = 0 のとき、 \frac{n}{k} を返す
    • n \% k = 0 のとき、 x = \lceil \frac{n \% k}{\lfloor \frac{n}{k} \rfloor + 1} \rceil として G(n - x \times (\lfloor \frac{n}{k} \rfloor + 1), k) を返す
  2. W = 0 とする
  3. 1 \le i \le N について W = W \oplus G(A_{i}, K_{i}) と更新していく
  4. W \ne 0 なら Takahashi、 W = 0 なら Aoki を出力する

計算量は O(N\sqrt{A})

公式解説

躓いた点

  • N \% K \ne 0 の場合の式を整理しきれず、回数の圧縮の発想が出なかった
  • 圧縮するための計算の実装ミスでWA連発

3/17: CODE FESTIVAL 2014 Easy D - 枕決め

供養

問題

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

解法

  • a_{j} の昇順にそれが好みとなる(i.e. x_{i} \le a_{j})まだ割り当てのない客のうち、 y_{i} が最も小さい客に割り当てていく
    • 割り当てられない a_{j} があったとき、そもそも割り当て不可能か、割り当てることが可能な客にはより小さい a_{j^{'}} が割り当てられている状態である
    • a_{j^{'}} \le a_{j} が割り当てられていた客 (x_{i}, y_{i}) に a_{j} を割り当てることで新規に (x_{i^{'}}, y_{i^{'}}) に割り当てられるとすると、 a_{j^{'}} \le a_{j} \le y_{i} および a_{j^{'}} \le y_{i^{'}} \lt a_{j} より y_{i^{'}} \lt y_{i} となるので、割り当て方と矛盾する
    • よって a_{j} に割り当てることで総数が増えることはないので最大値を得られる
    • Priority Queueで実現可能

実装は

  1. (x_{i}, y_{i}) を x_{i} の昇順にソートし (x^{'}_{i}, y^{'}_{i}) とする
  2. a_{j} を昇順にソートし a^{'}_{j} とする
  3. i = 0, c = 0 とする
  4. Priority Queue Q を用意する
    • pop時には要素の最小値を返し、その時の値を q_{0} とする
  5. j = 0, \dots, m - 1 について、以下のように更新する
    • i \lt n \land x^{'}_{i} \le a^{'}_{j} である間、 Q に y^{'}_{i} を追加し i をインクリメントする
    • |Q| \gt 0 \land q_{0} \lt a^{'}_{j} である間、 Q から q_{0} を取り除き続ける
      • a^{'}_{j - 1} 以前に Q に追加して条件から外れたものを除く
    • a^{'}_{j} \le q_{0} ならば c をインクリメントし、 q_{0} を取り除く
  6. c を出力する

計算量は O(n\mathrm{log}n + m\mathrm{log}m)

公式解説

躓いた点

  • y_{i} で昇順にソートして、greedyに割り当てられる最小の a_{j} を割り当てていったらWA

3/18: dwangoプログラミングコンテスト C - ゲーマーじゃんけん

供養

問題

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

解法

  • グーを r 人、パーを p 人、チョキを s 人が出す確率を P_{r, p, s}、その時の次のラウンドの人数を n_{r, p, s} とすると、求める期待値 E_{N} は E_{N} = 1 + \sum_{r = 0}^{N}\sum_{p = 0}^{N - r}P_{r, p, N - r - p} \times E_{n_{r, p, N - r - p}} となる
  • E_{1}, \dots, E_{N - 1} までが事前に求められていればある数 e, q を用いて (1 - q)E_{N} = e の形に整理できるので、 E_{N} = \frac{e}{1 - q} となる
  • P_{r, p, s}, n_{r, p, s} を前計算しておけば、 E_{2}, \dots, E_{N} までを順番に求めていくことができる
    • E_{1} = 0 である

実装は

  1. (N + 1) \times (N + 1) \times (N + 1) の配列 P を用意し、 P_{0, 0, 0} = 1 とする
  2. n = 1, \dots, N, 0 \le r \lt n, 0 \le p \lt n - r について、 s = n - r - p -1 とし、 P_{r + 1, p, s}, P_{r, p + 1, s}, P_{r, p, s + 1} にそれぞれ \frac{P_{r, p , s}}{3} を加算していく
  3. (N + 1) \times (N + 1) \times (N + 1) の配列 W を用意する
  4. n = 2, \dots, N, 0 \le r \le n, 0 \le p \le n - r について、 s = n - r - p とし、以下のように W_{r, p, s} を決める
    • r, p, s を昇順にソートした値を n_{0}, n_{1}, n_{2} とする
    • n_{2} = n \lor n_{0} = n_{2} のとき、 W_{r, p, s} = n
    • 上記以外で n_{0} = 0 のとき、 W_{r, p, s} = n_{1}
    • 上記2つ以外のとき、 W_{r, p, s} = n_{0}
  5. 長さ N + 1 の配列 E を用意する
  6. n = 2, \dots, N について以下のように計算する
    • e = 1, q = 0 とする
    • 0 \le r \le n, 0 \le p \le n - r について、以下のように計算する
      • s = n - r - p とする
      • W_{r, p, s} = n のとき、 P_{r, p, s} を q に加算する
      • それ以外のとき、 P_{r, p, s} \times E_{W_{r, p, s}} を e に加算する
    • E_{n} = \frac{e}{1 - q} とする
  7. E_{N} を出力する

計算量は O(N^{3})

公式解説

躓いた点

3/19: CODE FESTIVAL 2015 予選B D - マスと駒と色塗り

供養

問題

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

解法

  • S_{i} について昇順に候補に入れていき、候補の中で最初に移動する駒を使ってマスを黒くしていく
    • Priority Queueで実現可能

実装は

  1. (i, S_{i}, C_{i}) を S_{i} について昇順にソートしたものを P とする
  2. Priority Queue Q を用意し、 x = 0 とする
  3. 長さ N の配列 A を用意する
  4. P, Q がともに空になるまで以下の操作を繰り返す
    • Q が空なら P の先頭要素 (i, S_{i}, C_{i})を取り出して Q に追加する
    • Q の先頭要素 (i, S_{i}, C_{i}) を取り出し x = \mathrm{max}(x, S_{i}) とする
    • P が空であるか、 P の先頭要素 (j, S_{j}, C_{j}) について x + C_{i} \le S_{j} のとき、 x = x + C_{i}, A_{i} = x - 1 とする
    • それ以外のとき、 d = S_{j} - x とし、 (i, S_{i}, C_{i} - d), (j, S_{j}, C_{j}) を Q に追加する
  5. A_{0}, \dots, A_{N - 1} を1行ずつ出力する

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

公式解説

躓いた点

  • 操作順に求めようとして失敗

3/20: 天下一プログラマーコンテスト2014予選A C - 天下一文字列集合

供養

問題

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

解法

  • 各パターン P_{i} に対応する頂点 v_{i} と、任意の2頂点 v_{i}, v_{j} に対応する2つのパターン P_{i}, P_{j} に対応する文字列が存在するときに (v_{i}, v_{j}) 間に辺があるようなグラフ (V, E) を考える
  • V をそれぞれがクリークであるように分割したときに、分割数が最小になるようにすることと等しい
  • \mathit{DP}_{\emptyset} = 0, \mathit{DP}_{W \subseteq V \land W \ne \emptyset} = \infty とし、 U \subseteq V がクリークならば \mathit{DP}_{W \cup U} = \mathrm{min}(\mathit{DP}_{W} + 1, \mathit{DP}_{W \cup U}) のように更新していったときの \mathit{DP}_{V} が答えとなる

実装は

  1. n \times n の配列 G を用意する
  2. 0 \le i \lt n - 1, i + 1 \le j \lt n について、 P_{i}, P_{j} に合致するパターンが作れるならば G_{i, j} = \mathrm{true} とする
    • 0 \le k \lt m について、 p_{i, k} \ne p_{j, k} かつ p_{i, k} \ne * かつ p_{j, k} \ne * となる k が存在しなければ合致するパターンが作れる
  3. 長さ 2^{n} の配列 C を作る
  4. 1 \le x \lt 2^{n} について下記のように調べる
    • C_{x} = \mathrm{true} とする
    • 0 \le i \lt n - 1, i + 1 \le j \lt n について 0 \ne (x\; \mathrm{AND}\; 2^{i}) \land 0 \ne (x\; \mathrm{AND}\; 2^{j}) ならば C_{x} = C_{x} \land G_{i, j} とする
  5. 長さ 2^{n} の配列 \mathit{DP} を用意し、 \mathit{DP}_{0} = 0, \mathit{DP}_{i \ne 0} = n + 1 とする
  6. 1 \le i \lt 2^{n} について、 C_{i} = \mathrm{true} ならば \mathit{DP}_{i} = 1 とする
  7. i = 0, \dots, 2^{n} - 1, 0 \le x \lt 2^{n} について、 C_{x} = \mathrm{true} ならば \mathit{DP}_{i\; \mathrm{OR}\; x} = \mathrm{min}(\mathit{DP}_{i} + 1, \mathit{DP}_{i\; \mathrm{OR}\; x}) とする
  8. \mathit{DP}_{2^{n} - 1} を出力する

計算量は G の構築に O(n^{2}m)、 C の作成に O(2^{n}n^{2})、DPの計算に O((2^{n})^{2}) より、全体で O(n^{2}(2^{n} + m) + 4^{n})

公式解説

躓いた点

  • クリークの分割ができなかった

3/21: AtCoder Regular Contest 010 C - 積み上げパズル

供養

問題

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

解法

  • 最後に積んだ色と現在までに積んだ色集合ごとの最高点を保持したDPをする

実装は

  1. c_{i}, p_{i} と i をマッピングする配列 C, P を用意する
    • C_{c_{i}} = i, P_{i} = p_{i}
  2. m \times 2^{m} の配列 \mathit{DP}, \mathit{DP}^{-1} を用意する
    • n \times m \times 2^{m} の配列を作るとおそらくMLEになる
  3. 0 \le i \lt m について、 \mathit{DP}_{i, 0} = 0, \mathit{DP}_{i, j \ne 0} = \mathit{-Inf} とする
    • \mathit{-Inf} は取り得る点数に対して十分に小さければよい
  4. b_{1}, \dots, b_{n} について以下のようにDP表を更新する
    • \mathit{DP} を \mathit{DP}^{-1} にコピーする
    • b = C_{b_{k}} とする
    • 0 \le i \lt m, j = 0, \dots 2^{m} - 1 について
      • \mathit{DP}^{-1}_{i, j} = \mathit{-Inf} ならば何もしない
      • s = \mathit{DP}^{-1}_{i, j} + P_{b} とする
      • b = i \land j\; \mathrm{AND}\; 2^{b} \ne 0 ならば Y を s に加算する
      • j \ne 2^{m} - 1 \land j\; \mathrm{OR}\; 2^{b} = 2^{m} - 1 ならば Z を s に加算する
      • \mathit{DP}_{b, j\; \mathrm{OR}\; 2^{b}} = \mathrm{max}(s, \mathit{DP}_{b, j\; \mathrm{OR}\; 2^{b}}) とする
  5. \mathit{DP} の最大値を出力する

計算量は O(2^{m}mn)

公式解説

躓いた点

  • DPで保持する要素を思いつかなかった