そのうち誰かの役に立つ

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

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

競技プログラミング AtCoder DP

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

2/15: AtCoder Regular Contest 090 E - Avoiding Collision

供養

問題

Difficulty: 2282 (記事作成時点)

解法

S - T 間の最短距離を取るパス全ての組み合わせから高橋君と青木君が遭遇する組合せを引けばよい

  1. 各点 1 \le u \le N について S, T からの最短距離をDijkstraなどで求め、それぞれ D_{1, u}, D_{2, u} とする
  2. 配列 \mathit{DP}_{1} を用意し、 \mathit{DP}_{1} \lbrack S \rbrack = 1 とする
    • S から各点への最短路での到達パターン数を意味する
  3. 1 \le u \le N について、 D_{1, u} の昇順に見ていき、隣接点 v と距離 d の辺で繋がっているときに D_{1, v} - D_{1, u} = d ならば \mathit{DP}_{1} \lbrack v \rbrack = \mathit{DP}_{1} \lbrack v \rbrack + \mathit{DP}_{1} \lbrack u \rbrack とする
    • D_{1, v} - D_{1, u} = d ならば最短経路として利用されうる辺である
  4. 配列 \mathit{DP}_{2} を用意し、 \mathit{DP}_{2} \lbrack T \rbrack = 1 とする
    • T から各点への最短路での到達パターン数を意味する
  5. 1 \le u \le N について、 D_{1, u} の降順に見ていき、隣接点 v と距離 d の辺で繋がっているときに D_{1, u} - D_{1, v} = d ならば \mathit{DP}_{1} \lbrack v \rbrack = \mathit{DP}_{1} \lbrack v \rbrack + \mathit{DP}_{1} \lbrack u \rbrack とする
  6. S - T 間の最短距離を取るパス全ての組み合わせを A = \mathit{DP}_{1} \lbrack T \rbrack ^{2} とする
  7. D_{1, u} = D_{2, u} \land 2 \times D_{1, u} = D_{1, T} であるような 1 \le u \le N について、 \mathit{DP}_{1} \lbrack u \rbrack ^{2}\mathit{DP}_{2} \lbrack u \rbrack ^{2} を A から引く
    • 点 u 上で遭遇するパターン
  8. 1 \le i \le M について、辺 i が D_{1, u} \le D_{1, v} であるような (u, v) 間を距離 d で接続しているものとしたとき、 2 \times D_{1, u} \lt D_{1, T} \land 2 \times D_{2, v} \lt D_{1, T} \land D_{1, v} - D_{1, u} = d ならば \mathit{DP}_{1} \lbrack u \rbrack ^{2}\mathit{DP}_{2} \lbrack v \rbrack ^{2} を A から引く
    • 辺 i 上で遭遇するパターン
  9. A を出力する

計算量は最短路検索と最短距離でのソート、各点および各辺での遭遇判定をするので O(N\mathrm{log}N + M)

公式解説

躓いた点

  • 最初は遭遇しないパターンを数えようとしてWA
  • \mathit{DP}_{1}, \mathit{DP}_{2} の計算で 10^{9} + 7 の剰余を取り忘れてWA
  • \mathit{DP}_{2} を D_{2, u} の昇順で作ってWA
  • 公式解説の日本語の書き方が曖昧で英語の方を読むまでWA大量生産

2/16: AtCoder Regular Contest 071 F - Infinite Sequence

供養

問題

Difficulty: 2283 (記事作成時点)

解法

  • 1 \le k \le n について、 \mathit{DP} \lbrack k \rbrack を a_{n - k + 1}, \dots, a_{n} までのパターン数とする
  • \mathit{DP} \lbrack 1 \rbrack = n, \mathit{DP} \lbrack 2 \rbrack = n^{2} である
  • k \ge 3 について、 a_{n - k + 1} = 1 ならば a_{n - k + 2}, \dots, a_{n} は \mathit{DP} \lbrack k - 1 \rbrack のときに求めたパターンとなる
  • a_{n - k + 1} = x \neq 1 \land a_{n - k + 2} = y \neq 1 のとき、 a_{n - k + 2}, \dots, a_{n} はすべて y となり、このような (x, y) の組合せは (n - 1)^{2} 通り
  • a_{n - k + 1} = x \neq 1 \land a_{n - k + 2} = 1 のとき、 a_{n - k + 2}, \dots, a_{n - k + x + 1} まで1が連続し、 x + 1 \lt k ならばその後は \mathit{DP} \lbrack k - x - 1 \rbrack のときに求めたパターンとなる
    • k \le x + 1 ならば以降は1が連続するパターンのみで、そのような x は n - k + 2 通り
  • 上記を漸化式にすると \mathit{DP} \lbrack k \rbrack = \mathit{DP} \lbrack k - 1 \rbrack + (n - 1)^{2} + \sum_{i = 1}^{k - 3}\mathit{DP} \lbrack i \rbrack + n - k + 2

実装は

  1. 配列 \mathit{DP} を用意し、 \mathit{DP} \lbrack 1 \rbrack = n, \mathit{DP} \lbrack 2 \rbrack = n^{2} とする
  2. 配列 S を用意し、 S \lbrack 1 \rbrack = n, S \lbrack 2 \rbrack = n^{2} + n とする
    • S \lbrack i \rbrack は \mathit{DP} \lbrack 1 \rbrack から \mathit{DP} \lbrack i \rbrack までの累積和を意味する
  3. k = 3, \dots, n について、 \mathit{DP} \lbrack k \rbrack = \mathit{DP} \lbrack k - 1 \rbrack + (n - 1)^{2} + S \lbrack k - 3 \rbrack + n - k + 3, S \lbrack k \rbrack = S \lbrack k - 1 \rbrack + \mathit{DP} \lbrack k \rbrack で更新していく
  4. \mathit{DP} \lbrack n \rbrack を出力する

計算量は O(n)

公式解説

躓いた点

  • 漸化式を立てられなかった

2/17: AtCoder Grand Contest 021 D - Reversed LCS

供養

問題

Difficulty: 2288 (記事作成時点)

解法

  • 最長共通部分文字列の少なくとも1つは回文である
    • 長さ k の回文でない部分文字列 T = t_{1}, \dots, t_{k} が最長共通部分文字列とする
    • S を反転した S^{'} にも T が含まれることから、 S には T^{'} = t_{k}, \dots, t_{1} も含まれる
    • T, T^{'} を S の実際の位置で T = s_{i_{1}}, \dots s_{i_{k}} (k \lt k^{'} \Rightarrow i_{k} \lt i_{k^{'}}) および T^{'} = s_{j_{k}}, \dots, s_{j_{1}} (k \lt k^{'} \Rightarrow j_{k} \gt j_{k^{'}}) としたとき、
      • i_{k} \lt j_{k} ならば、 s_{i_{1}}, \dots, s_{i_{k}}, s_{j_{k}}, \dots, s_{j_{1}} は回文かつ S にも S^{'} にも含まれる長さ 2k の文字列である
      • i_{1} \ge j_{1} ならば、 s_{j_{k}}, \dots, s_{j_{1}}, s_{i_{2}}, \dots, s_{i_{k}} は回文かつ S にも S^{'} にも含まれる長さ 2k - 1 の文字列である
      • ある数 1 \le k^{'} \lt k が存在し、 i_{k^{'}} \lt j_{k^{'}} \land i_{k^{1} + 1} \ge j_{k^{'} + 1} ならば、 T_{1} = s_{i_{1}}, \dots, s_{i_{k^{'}}}, s_{j_{k^{'}}}, \dots, s_{j_{1}} と T_{2} = s_{j_{k}}, \dots, s_{j_{k^{'}}}, s_{i_{k^{'} + 1}}, \dots, s_{i_{k}} は回文かつ S にも S^{'} にも含まれ、 |T_{1}| + |T_{2}| = 2k - 1 より |T_{1}| \ge k もしくは |T_{2}| \ge k である
    • 上記より、長さ k 以上の回文であるような共通部分文字列が存在する
  • K 文字まで変更可能という条件下での最長の回文をDPで求める
    • \mathit{DP} \lbrack l \rbrack \lbrack r \rbrack \lbrack k \rbrack を s_{l}, \dots, s_{r} の範囲で k 文字まで変更可能な条件下での最長の回文とする

実装は

  1. 二次元配列 L を用意し、 1 \le i \le N について L \lbrack \mathrm{int}(s_{i}) - 97 \rbrack \lbrack i \rbrack = i とする
    • \mathrm{int}(s_{i}) は s_{i} をascii codeに変換したもの
  2. 0 \le i \lt 26, j = N - 1, \dots, 1 について、 L \lbrack i \rbrack \lbrack j \rbrack = 0 ならば L \lbrack i \rbrack \lbrack j \rbrack = L \lbrack i \rbrack \lbrack j + 1 \rbrack とする
    • L \lbrack i \rbrack \lbrack j \rbrack が文字種 i が j 以降最初に表れる位置を意味する
    • 表記の簡略化のため L \lbrack \mathrm{int}(s_{i}) - 97 \rbrack \lbrack j \rbrack を L_{i, j} と書く
  3. 三次元DP表 \mathit{DP} を用意し、 1 \le l \le N, 0 \le k \le K について \mathit{DP} \lbrack l \rbrack \lbrack l + k + 1 \rbrack \lbrack k \rbrack = k + 1 とする
  4. k = 0, \dots, K, l = N, \dots, 1, r = l + 1, \dots, N について下記から最大値を選ぶ形で \mathit{DP} \lbrack l \rbrack \lbrack r \rbrack \lbrack k \rbrack を更新していく
    • \mathit{DP} \lbrack l \rbrack \lbrack r - 1 \rbrack \lbrack k \rbrack
    • \mathit{DP} \lbrack l + 1 \rbrack \lbrack r \rbrack \lbrack k \rbrack
    • \mathit{DP} \lbrack l \rbrack \lbrack r \rbrack \lbrack k - 1 \rbrack
    • \mathit{DP} \lbrack L_{k, l} + 1 \rbrack \lbrack r - 1 \rbrack \lbrack k \rbrack + 2
      • s_{r} を変換せずに回文に加える
    • \mathit{DP} \lbrack l + 1 \rbrack \lbrack r - 1 \rbrack \lbrack k - 1 \rbrack + 2
      • s_{r} を変換して回文に加える
  5. \mathit{DP} \lbrack 1 \rbrack \lbrack N \rbrack \lbrack K \rbrack を出力する

計算量は O(|S|^{2}K)

公式解説

躓いた点

  • 最長共通部分文字列が回文という性質に気付かなかった
  • DPを64 bit intで作ったらMLE

2/18: M-SOLUTIONS プロコンオープン E - Product of Arithmetic Progression

供養

問題

Difficulty: 2289 (記事作成時点)

解法

  • d = 1 のとき、 \prod_{X = x}^{x + n - 1}X = \frac{(x + n - 1)!}{(x - 1)!} と表せる
  • d \neq 0 のとき、 x \times (x + d) \times \dots \times (x + (n - 1)d) の全ての項を d で割ると \frac{x}{d} \times (\frac{x}{d} + 1) \times \dots \times (\frac{x}{d} + n - 1) となるので、上記より \frac{(\frac{x}{d} + n - 1)!}{(\frac{x}{d} - 1)!} \times d^{n} で求められる
  • d^{-1}, (\frac{x}{d} + n - 1)!, (\frac{x}{d} - 1)!^{-1} を前計算しておけばよい
    • \frac{x}{d}, \dots, \frac{x}{d} + n - 1 の中に p = 1000003 の倍数があると剰余は0になるので、前計算の計算量は O(p) で抑えられる

実装は

  1. 1 \le k \lt p について k^{-1}, k!, k!^{-1} を計算する
  2. d = 0 のとき、 x^{n} を出力する
    • x, x^{2}, x^{4}, \dots, x^{2 \lceil \mathrm{log}n \rceil} を計算して必要なものをかけ合わせれば O(\mathrm{log}n) で求められる
  3. d \neq 0 のとき、 X = x \times d^{-1} とする
  4. X\; \mathrm{mod}\; p \equiv 0 \lor p \lt X + n ならば0を出力し、そうでなければ (X + n - 1)! \times (X - 1)!^{-1} \times d^{n} を出力する
  5. x_{i}, d_{i}, n_{i}\; (1 \le i \le Q) について、上記を求めて出力していく

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

公式解説

躓いた点

  • d = 1 ならば簡単に計算できることに思い至らなかった
  • d で割って差を1にする発想も出なかった

2/19: AtCoder Beginner Contest 155 D - Pairs

供養

問題

Difficulty: 1827 (記事作成時点)

解法

  • ある数 X について、 A_{i} \times A_{j} \le X であるような (i, j) の組の数を f(X) とし、 f(X - 1) \lt K, f(X) \ge K であるような X を二分探索で求める
  • f(X) は昇順にソートした A について、 i \lt j であるような各 A_{i}, A_{j} について下記条件を満たす範囲を二分探索で求めて和を取ればよい
    • A_{i} = 0 のとき、 X \ge 0 ならば全て、 X \lt 0 なら無し
    • A_{i} \gt 0 のとき、 A_{j} \le \lfloor \frac{X}{A_{i}} \rfloor
    • A_{i} \lt 0 のとき、 A_{j} \ge \lceil \frac{X}{A_{i}} \rceil

実装は

  1. A を昇順にソートする
  2. M = \mathrm{max}(A_{1} \times A_{2}, A_{N - 1} \times A_{N}), m := \mathrm{min}(A_{1} \times A_{2}, A_{1} \times A_{N}, A_{N - 1} \times A_{N}) - 1 とする
    • f(M) = \frac{N(N - 1)}{2}, f(m) = 0 となる
  3. A_{i} \le x であるような要素数を求める関数を g(x) とする
  4. f(X) = \sum_{i = 1}^{N}S_{i} を下記のように求める関数とする
    • A_{i} = 0 のとき
      • X \lt 0 ならば S_{i} = 0
      • X \ge 0 ならば S_{i} = N - i
    • A_{i} \gt 0 のとき
      • S_{i} = \mathrm{max}(g(\lfloor \frac{X}{A_{i}} \rfloor) - i, 0)
    • A_{i} \lt 0 のとき
      • S_{i} = \mathrm{max}(N - \mathrm{max}(g(\lceil \frac{X}{A_{i}} \rceil - 1), i), 0)
        • 各言語の除算の挙動の違いに注意
  5. \lbrack m, M \rbrack の範囲で f(X - 1) \lt K \land f(X) \ge K であるような X を求め、 X を出力する

計算量は A^{'} を A_{i} の最大値としたときに O(N\mathrm{log}N\mathrm{log}A^{'})

公式解説

躓いた点

  • A_{i} \lt 0 の場合の処理でバグを埋め込んでWA

2/20: AtCoder Beginner Contest 155 E - Payment

供養

問題

Difficulty: 1653 (記事作成時点)

解法

  1. N = n_{1} \dots n_{|N|} とする
  2. \mathit{DP} \lbrack 0 \rbrack \lbrack 0 \rbrack = 0, \mathit{DP} \lbrack 0 \rbrack \lbrack 1 \rbrack = 1 とする
  3. 1 \le k \le |N| について、下記のようにDP表を更新する
    \mathit{DP} \lbrack k \rbrack \lbrack 0 \rbrack = \mathrm{min}(\mathit{DP} \lbrack k - 1 \rbrack \lbrack 0 \rbrack + n_{k}, \mathit{DP} \lbrack k - 1 \rbrack \lbrack 1 \rbrack + 10 - n_{k})
    \mathit{DP} \lbrack k \rbrack \lbrack 1 \rbrack = \mathrm{min}(\mathit{DP} \lbrack k - 1 \rbrack \lbrack 0 \rbrack + n_{k} + 1, \mathit{DP} \lbrack k - 1 \rbrack \lbrack 1 \rbrack + 9 - n_{k})
    • k + 1 桁目以降を考えずに、 k 桁目をちょうど支払った場合と、 k 桁目を1多く支払った場合を作っていく
  4. \mathit{DP} \lbrack |N| \rbrack \lbrack 0 \rbrack を出力する

計算量は O(|N|)

公式解説

躓いた点

  • DP作れず

2/21: AtCoder Regular Contest 083 E - Bichrome Tree

供養

問題

Difficulty: 2293 (記事作成時点)

解法

  • ある点 v を根とする部分木 T_{v} において、 v と同色の点の重みの和を x_{v}、異なる色の点の重みの合計を y_{v} とする
    • 問題の条件より x_{v} = X_{v}
    • T_{v} の彩色を全て反転させても x_{v}, y_{v} の値は変わらない
  • ある点 u の子 v_{1}, \dots, v_{c_{u}} それぞれについて x_{v}, y_{v} が求められているとき、 x_{u} は 1 \le v \le c_{u} それぞれについて x_{v} もしくは y_{v} のどちらかを採用した和 x^{'} に u の重みを足した値となる
    • x^{'} \le X_{u} となるような選び方が存在するかを判定する
  • y_{v} は条件を満たす選び方で最小の物だけを考えればよい
    • y_{v} \lt y_{v}^{'} なる y_{v}^{'} を使った時に条件を満たす選び方が存在するならば、 y_{v}^{'} を y_{v} に置き換えても条件を満たす選び方となる
  • よって、条件を満たす場合は y_{v} の最小値を求める

実装は

  1. 1 \le v \le N について、 0 \le k \le X_{v} までを持つDP表を2つ用意し \mathit{DP}_{v, 1}, \mathit{DP}_{v, 2} とする
    • 表記の簡略化のため、 \mathit{DP}_{v, j} の k 番目の要素を \mathit{DP}_{v, j, k} と表記する
  2. 十分大きな数 M を用意し、 1 \le v \le N について \mathit{DP}_{v, 1, 0} = 0、それ以外の要素は M で初期化する
  3. v = N, \dots, 2 について、以下のようにDPを更新していく
    • y_{v} = \mathrm{min}(\mathit{DP}_{v, 1}) とし、 y_{v} = M ならば IMPOSSIBLE を出力して終了
    • 0 \le k \le X_{P_{v}} について \mathit{DP}_{P_{v}, 2, k} = M で初期化する
    • 0 \le k \le X_{P_{v}} について、 k + x_{v} \le X_{P_{v}} ならば \mathit{DP}_{P_{v}, 2, k + x_{v}} = \mathrm{min}(\mathit{DP}_{P_{v}, 1, k} + y_{v}, \mathit{DP}_{P_{v}, 2, k + x_{v}})
    • 0 \le k \le X_{P_{v}} について、 k + y_{v} \le X_{P_{v}} ならば \mathit{DP}_{P_{v}, 2, k + y_{v}} = \mathrm{min}(\mathit{DP}_{P_{v}, 1, k} + x_{v}, \mathit{DP}_{P_{v}, 2, k + y_{v}})
    • 0 \le k \le X_{P_{v}} について、 \mathit{DP}_{P_{v}, 1, k} = \mathit{DP}_{P_{v}, 2, k}
  4. y_{1} = \mathrm{min}(\mathit{DP}_{1, 1}) \le X_{1} ならば POSSIBLE を、そうでなければ IMPOSSIBLE を出力

計算量は X^{'} を X_{v} の最大値として O(NX^{'})

公式解説

躓いた点

  • 貪欲法で y_{v} の最小化ができると思ったがWA