そのうち誰かの役に立つ

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

AtCoderチャレンジ供養会場(2020/02/01-2020/02/07)

競技プログラミング AtCoder Ford-Fulkerson DP BIT

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

2/1: AtCoder Regular Contest 074 F - Lotus Leaves

供養

問題

Difficulty: 2205 (記事作成時点)

解法

最小カットに帰着する方法と、 S, T 間の局所点連結度を求める方法がある

解法1: 最小カット

  1. 各マスに対応する点および行 1, \dots, H、列 1, \dots, W に対応する点を用意する
  2. 各マス a_{ij} について以下のように有効辺を張る
    • a_{ij} =S のとき、 a_{ij} に対応する点から行 i、列 j それぞれに対応する点へ容量 \mathit{Inf} の辺を張る
    • a_{ij} =T のとき、行 i、列 j それぞれに対応する点から a_{ij} に対応する点へ容量 \mathit{Inf} の辺を張る
    • a_{ij} =o のとき、 a_{ij} に対応する点から行 i、列 j それぞれに対応する点へ双方向に容量 1 の辺を張る
    • a_{ij} =. のとき、何もしない
  3. 上記で構成されたグラフについてのS-T間の最大流問題をFord-Fulkersonなどで解き、答えを F とする
  4. F \ge \mathit{Inf} ならば -1 を出力し、そうでなければ F を出力する

解法2: 局所点連結度

  1. 1 \le i \le H, 1 \le j \le W について、マス (i, j) を点 x_{ij} = (i - 1)W + j - 1 とし、 a_{ij} = . ならば v_{x_{ij}} = 0、それ以外ならば v_{x_{ij}} = 1 とする
  2. v_{x_{ij}} = 1 のとき、同行もしくは同列で蓮のあるマスに対応する点と無向辺を張る
    • 0 \le h \lt i - 1 について、 v_{hW + j - 1} = 1 である点と無向辺を張る
    • 0 \le w \lt j - 1 について、 v_{(i - 1)W + w} = 1 である点と無向辺を張る
  3. a_{i_{s}j_{s}} = S であるような v_{x_{i_{s}j_{s}}} と a_{i_{t}j_{t}} = T であるような v_{x_{i_{t}j_{t}}} が直接結ばれている場合は -1 を出力して終了
  4. v_{x_{i_{s}j_{s}}}, v_{x_{i_{t}j_{t}}} 間の点疎なパスの本数を出力する
    • v_{x_{i_{s}j_{s}}}, v_{x_{i_{t}j_{t}}} 間の最短パスを1本求め、そこに登場する点を削除する
    • 上記を2点間が非連結となるまで繰り返す

計算量は最小カットのグラフの辺の数が O(HW) 、フロー増加パスの長さが O(H ; W) 、最大フローが次数で抑えられるので O(HW(H + W)^{2})、局所点連結度を求める方法が、各頂点の次数が O(H + W) に抑えられることから最短パスを求めるBFSを O(HW(H + W)) で実施でき、局所点連結度も次数で抑えられるので O(HW(H + W)^{2})

公式解説

躓いた点

  • 局所点連結度を求めたらACしたが最小カットの復習をしたかった
  • Ford-Fulkersonの実装が甘くMLE、TLE、WAの大量生産

2/2: AtCoder Grand Contest 022 C - Remainder Game

供養

問題

Difficulty: 2209 (記事作成時点)

解法

  1. 1 \le i \le N について、 a_{i} = b_{i} \lor a_{I} \gt 2b_{i} でないものがあったときは -1 を出力して終了
  2. 0 \le a_{i}, b_{i} \le 50 より v_{0}\, \dots, v_{50} を用意する
  3. 1 \le k \le 49 および 0 \le i \le 50 について、 v_{i} \to v_{i\; \mathrm{mod}\; k} に有効辺を張る
    • 多重辺を許容する
  4. k = 49, \dots, 1 の順に、 0 \le v \le 50 について v_{v} \to v_{v\; \mathrm{mod}\; k} の辺を取り除いていく
  5. 1 \le i \le N について v_{a_{i}} から v_{b_{i}} に到達できなくなった場合、最後に取り除いた k を固定する
    • 0 \le v \le 50 について v_{v} \to v_{v\; \mathrm{mod}\; k} の辺を取り除かずに残す
  6. 最後に残った k について、 \sum_{k}2^{k} を出力する

計算量は a_{i}, b_{i} の最大値を A として、到達性の判定に O(NA^{2}) 、全体で O(NA^{3})

公式解説

躓いた点

  • 最小化のための方針立たず

2/3: Tenka1 Programmer Beginner Contest 2019 D - Three Colors

供養

問題

Difficulty: 2227 (記事作成時点)

解法

全体から条件を満たさないパターン数を引く

  1. S = \sum_{i = 1}^{N}a_{i} とする
  2. \mathit{DP1} \lbrack 0 \rbrack \lbrack 0 \rbrack = 1 とする
    • 三角形の3辺すべてを固定したときに、 k = 1, \dots, i までの a_{k} で長辺の長さがちょうど j になるパターン数を \mathit{DP1} \lbrack i \rbrack \lbrack j \rbrack で表す
  3. \mathit{DP2} \lbrack 0 \rbrack \lbrack 0 \rbrack = 1 - S\; \mathrm{mod}\; 2 とする
    • 三角形の長辺のみを固定したときに、 k = 1, \dots, i までの a_{k} で長辺の長さがちょうど j になるパターン数を \mathit{DP2} \lbrack i \rbrack \lbrack j \rbrack で表す
    • S が偶数の時のみ必要
  4. i = 1, \dots, N について、下記のようにDPを更新する
    • j = 0, \dots, Sについて、 \mathit{DP1} \lbrack i \rbrack \lbrack j \rbrack = 2 \times \mathit{DP1} \lbrack i - 1 \rbrack \lbrack j \rbrack
    • j = 0, \dots, S - a_{i}について、 \mathit{DP1} \lbrack i \rbrack \lbrack j + a_{i} \rbrack = \mathit{DP1} \lbrack i - 1 \rbrack \lbrack j + a_{i} \rbrack + \mathit{DP1} \lbrack i - 1 \rbrack \lbrack j \rbrack
    • j = 0, \dots, Sについて、 \mathit{DP2} \lbrack i \rbrack \lbrack j \rbrack = \mathit{DP2} \lbrack i - 1 \rbrack \lbrack j \rbrack
    • j = 0, \dots, S - a_{i}について、 \mathit{DP2} \lbrack i \rbrack \lbrack j + a_{i} \rbrack = \mathit{DP2} \lbrack i - 1 \rbrack \lbrack j + a_{i} \rbrack + \mathit{DP2} \lbrack i - 1 \rbrack \lbrack j \rbrack
  5. 3^{N} - 3 \times \sum_{j = \lfloor \frac{S}{2} \rfloor + 1}^{S}\mathit{DP1} \lbrack N \rbrack \lbrack j \rbrack + 3 \times \mathit{DP2} \lbrack N \rbrack \lbrack \lfloor \frac{S}{2} \rfloor \rbrack を出力する

計算量は O(NS)

公式解説

躓いた点

  • 重複分もDP1つでまとめて計算しようとしたらWA

2/4: AtCoder Grand Contest 017 D - Game on Tree

供養

問題

Difficulty: 2233 (記事作成時点)

解法

部分木のGrundy数について、以下の証明を行う:
点 r を根とする木 T のGrundy数を G(T) としたとき、 T を部分木に持ち、 r を唯一の子とするような点 r^{'} を根とする木 T^{'} のGrundy数 G(T^{'}) は G(T^{'}) = G(T) + 1
\because T の頂点数 n に関する帰納法を用いる
basis: n = 1 のとき、 G(T) = 0 かつ G(T^{'}) = 1 により成立
inductive step: n \le k の任意の木について成り立つと仮定する。 n = k + 1 の木 T から T^{'} を構成し、 T^{'} から任意の辺を除いて作られる r^{'} を含む部分木は、 r^{'} のみもしくは T の部分木 T^{''} に r^{'} を根として加えたものである。ここで、 r^{'} のみの部分木のGrundy数は0、 T^{''} + r^{'} の部分木のGrundy数は仮定より G(T^{''}) + 1 となる。Grundy数の定義よりGrundy数が 0, \dots, G(T) - 1 となるような T の部分木が存在するので、 T^{'} の部分木は 0, \dots, G(T) - 1 + 1 のGrundy数をとることができることから、 G(T^{'}) = G(T) + 1 となり成立

実装は単純

  1. 部分木の頂点を r として、以下のように再帰的にGrundy数 G(r) を求める
    • r が葉ならば G(r) = 0
    • r に1つの子 c がいる場合、 G(r) = G(c) + 1
    • r に2つ以上の子 c_{1}, \dots, c_{\mathit{ch}_{r}} がいる場合、 G(r) = \bigl( G(c_{1}) + 1) \oplus \dots \oplus (G(c_{\mathit{ch}_{r}}) + 1) \bigr)
  2. G(1) \neq 0 ならば Alice 、そうでないならば Bob を出力

計算量は O(N)

公式解説

躓いた点

  • Grundy数の性質を理解していない
  • 部分木の分割を間違えてWA

2/5: CODE FESTIVAL 2016 qual C D - Friction

供養

問題

Difficulty: 2242 (記事作成時点)

解法

  • 1 \le i, j \lt W, i \neq j であるような i 列目と i + 1 列目の間に発生するコストと、 j 列目と j + 1 列目の間に発生するコストは独立して計算できる
    • 共通する列がある場合、共通列をどれだけ沈めたかが一致するようにお互いの操作の順番を決めることができる
  • ある2列間で発生するコストの計算は、左の列を x 個、右の列を y 個沈めるために必要な最小コストを求めるDPで計算できる
    • 左を x - 1 個、右を y 個沈めた状態からの遷移と、左を x 個、右を y - 1 個沈めた状態からの遷移で小さい方をとればよい
  • 遷移のためのコストを前計算しておくことで高速化できる

実装は

  1. w 列目と w + 1 列目の間のコストを計算するとする
  2. 0 \le i, j \lt H について、 c_{H - i, w} = c_{H - j, w + 1} ならば C \lbrack i \rbrack \lbrack j \rbrack = 1 とする
  3. i = H, \dots, 1, j = H, \dots, 1 について、 C \lbrack i - 1 \rbrack \lbrack j - 1 \rbrack = C \lbrack i -1 \rbrack \lbrack j -1 \rbrack + C \lbrack i \rbrack \lbrack j \rbrack のように計算していく
  4. \mathit{DP} \lbrack 0 \rbrack \lbrack 0 \rbrack = 0 とする
  5. i = 1, \dots, H について、 \mathit{DP} \lbrack i \rbrack \lbrack 0 \rbrack = \mathit{DP} \lbrack i - 1 \rbrack \lbrack 0 \rbrack + C \lbrack i - 1 \rbrack \lbrack 0 \rbrack, \mathit{DP} \lbrack 0 \rbrack \lbrack i \rbrack = \mathit{DP} \lbrack 0 \rbrack \lbrack i - 1 \rbrack + C \lbrack 0 \rbrack \lbrack i - 1 \rbrack と計算する
  6. i = 1, \dots, H, j = 1, \dots, H について、 \mathit{DP} \lbrack i \rbrack \lbrack j \rbrack = \mathrm{min}(\mathit{DP} \lbrack i - 1 \rbrack \lbrack j \rbrack + C \lbrack i - 1 \rbrack \lbrack j \rbrack, \mathit{DP} \lbrack i \rbrack \lbrack j - 1 \rbrack + C \lbrack i \rbrack \lbrack j - 1 \rbrack) と計算していく
  7. \mathit{DP} \lbrack H \rbrack \lbrack H \rbrack を w 列目と w + 1 列目の間のコストとして、各列間のコストの合計を出力する

計算量は1回あたりの前計算とDPが O(H^{2}) で、各列間繰り返すので O(H^{2}W)

公式解説

躓いた点

  • DPの計算を上手く書けずにWA

2/6: AtCoder Regular Contest 097 E - Sorted and Sorted

供養

問題

Difficulty: 2246 (記事作成時点)

解法

記述の簡単のため、黒の小さいものから i 番目のボールのことを B_{i}、白の小さいものから j 番目のボールのことを W_{j} とする

  1. \mathit{CostB} \lbrack i \rbrack \lbrack j \rbrack を B_{1}, \dots, B_{i} および W_{1}, \dots, W_{j} を左から任意の順番に並べたときに B_{i + 1} を確定させるための交換回数とする
    • 同様に \mathit{CostW} \lbrack i \rbrack \lbrack j \rbrack を定義する
    • 以降、 \mathit{CostB} でおこなう計算を同様に \mathit{CostW} でもおこなう
  2. 1 \le i \le N について、 \mathit{CostB} \lbrack i - 1 \rbrack \lbrack 0 \rbrack に B_{i + 1}, \dots, B_{N} で B_{i} より前にあるものの個数を入れる
    • 転倒数なのでBITで計算可能
  3. 1 \le i \le N, j = 1, \dots, N について、 \mathit{CostB} \lbrack i - 1 \rbrack \lbrack j \rbrack = \mathit{CostB} \lbrack i - 1 \rbrack \lbrack j - 1 \rbrack + s_{i, j} とする
    • s_{i, j} は B_{i} が W_{j} より前なら1、そうでないなら0
  4. \mathit{DP} \lbrack 0 \rbrack \lbrack 0 \rbrack = 0 とする
  5. i = 0, \dots, N, j = 0, \dots, N について、 \mathit{DP} \lbrack i \rbrack \lbrack j \rbrack = \mathrm{min}(\mathit{DP} \lbrack i - 1 \rbrack \lbrack j \rbrack + \mathit{CostB} \lbrack i - 1 \rbrack \lbrack j \rbrack, \mathit{DP} \lbrack i \rbrack \lbrack j - 1 \rbrack + \mathit{CostW} \lbrack i \rbrack \lbrack j - 1 \rbrack) と計算していく
  6. \mathit{DP} \lbrack N \rbrack \lbrack N \rbrack を出力する

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

公式解説

躓いた点

  • 異なる色についてのコスト計算が思いつかず

2/7: AtCoder Grand Contest 015 C - Nuske vs Phantom Thnook

供養

問題

Difficulty: 2254 (記事作成時点)

解法

青マス同士の隣接関係を辺としてグラフを作ると森になるので、連結成分の数は青マスの数から辺の数を引いたものであるから二次元累積和で求められる

  1. 0 \le i \le N, 0 \le j \le M について、 V \lbrack i \rbrack \lbrack j \rbrack をグリットの左上から i 行 j 列までの青マスの累積和とする
  2. 0 \le i \le N, 0 \le j \le M について、 E_{V} \lbrack i \rbrack \lbrack j \rbrack をグリットの左上から i 行 j 列までの垂直方法の辺の累積和とする
    • マス (i - 1, j) と マス (i, j) がともに青ならば E_{V} \lbrack i \rbrack \lbrack j \rbrack = E_{V} \lbrack i - 1 \rbrack \lbrack j \rbrack + 1
  3. 0 \le i \le N, 0 \le j \le M について、 E_{H} \lbrack i \rbrack \lbrack j \rbrack をグリットの左上から i 行 j 列までの水平方向の辺の累積和とする
  4. [1 \le i \le Q] について、指定されたエリア内の青マスの数 V、垂直方向の辺の数 E_{V}、水平方向の辺の数 E_{H} を下記のように求め、 V - E_{V} - E_{H} を出力していく
    • V = V \lbrack x_{1, 1} - 1 \rbrack \lbrack y_{1, 1} - 1 \rbrack + V \lbrack x_{2, 2} \rbrack \lbrack x_{2, 2} \rbrack - V \lbrack x_{1, 1} - 1 \rbrack \lbrack y_{2, 2} \rbrack - V \lbrack x_{2, 2} \rbrack \lbrack y_{1, 1} - 1 \rbrack
    • E_{V} = E_{V} \lbrack x_{1, 1} \rbrack \lbrack y_{1, 1} - 1 \rbrack + E_{V} \lbrack x_{2, 2} \rbrack \lbrack x_{2, 2} \rbrack - E_{V} \lbrack x_{1, 1} \rbrack \lbrack y_{2, 2} \rbrack - E_{V} \lbrack x_{2, 2} \rbrack \lbrack y_{1, 1} - 1 \rbrack
    • E_{H} = E_{H} \lbrack x_{1, 1} - 1 \rbrack \lbrack y_{1, 1} \rbrack + E_{H} \lbrack x_{2, 2} \rbrack \lbrack x_{2, 2} \rbrack - E_{H} \lbrack x_{1, 1} - 1 \rbrack \lbrack y_{2, 2} \rbrack - E_{H} \lbrack x_{2, 2} \rbrack \lbrack y_{1, 1} \rbrack

計算量は前処理に O(NM)、各クエリが定数時間なので O(NM + Q)

公式解説

躓いた点

  • 辺の数で森を数える発想がなかった