そのうち誰かの役に立つ

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

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

競技プログラミング AtCoder DP Priority Queue BIT

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

4/22: DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選 C - 特別講演「括弧列と塗り分け」

供養

問題

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

解法

  • S から頂点数 \frac{|S|}{2} + 1 の木を以下のように作成できる
    • 頂点0を根とし、下記操作で作られる部分木の根を全て0の子とする
    • i 番目の ( で始まる括弧内に j 番目の ( で始まる括弧を含むとき、 i を j の親とする
  • 木の各頂点に赤もしくは青の石を2つ割り当て、すべての部分木で部分木に含まれる赤い石の数 R と青い石の数 B の差が K 以下になるような石の置き方を考える
  • 条件を満たしつつ、頂点 i を根とする部分木に j 個の赤い石がある置き方を \mathit{DP}_{i, j} としてDPをする

実装は

  1. N = \frac{|S|}{2} とし、長さ N + 1 の配列 P を用意する
  2. 頂点数 N + 1 の木 T を下記のように作る
    • u = 0, v = 1 とする
    • S を先頭から見ていき、現在見ている文字 s について以下のように処理する
      • s =( のとき、以下の操作をする
        • P_{v} = u とする
        • T_{u} に v を追加する
        • u = v とする
        • v をインクリメントする
      • s =) のとき、 u = P_{u} とする
  3. T を点0から幅優先探索し、発見順に並べたものを Q とする
  4. 長さ N + 1 の配列 V を用意し、 V_{i} を点 i を根とする部分木の頂点数とする
    • V_{i \ne 0} = 1 とし、 v を Q の逆順に見ていき V_{P_{v}} に V_{v} を加算していけばよい
  5. (N + 1) \times 2 \times (2N + 1) のDP表 \mathit{DP} を用意し、 \mathit{DP}_{i, 0, 0} = 1、 i \ne 1 について \mathit{DP}_{i, 0, 1} = 2, \mathit{DP}_{i, 0, 2} = 1 とする
  6. 長さ N + 1 の配列 M を用意する
  7. i = N, \dots, 1 について下記のようにDP表を更新する
    • v = Q_{i}, u = P_{v} とする
    • 0 \le k \le 2V_{u} について、以下の操作を実施する
      • x = \mathit{DP}_{u, M_{u}, k} とし、 x = 0 ならば何もせず次に行く
      • \mathrm{max}(V_{v} - \lfloor \frac{K}{2} \rfloor, 0) \le l \le \mathrm{min}(V_{v} + \lfloor \frac{K}{2} \rfloor, 2N) について、 y = \mathit{DP}_{v, M_{v}, l} とし、 xy を \mathit{DP}_{u, 1 - M_{u}, k + l} に加算する
      • \mathit{DP}_{u, M_{u}, k} = 0 とする
    • M_{u} = 1 - M_{u} とする
  8. \sum_{j = 0}^{2N}\mathit{DP}_{0, M_{0}, j} を出力する

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

公式解説

躓いた点

  • DP更新時の畳み込みの整理に苦戦した
  • 木の作成でバグを作ってWA

4/23: 第2回 ドワンゴからの挑戦状 予選 D - 庭園

供養

問題

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

解法

  • 長方形を1つ作るときの左端 l と右端 r を決め打って、そのときの最大値を S_{l, r} で持つ
    • h = 1, \dots, H について、1行目から h 行目で作る長方形で行 h を使う場合の最大の面積と、制約なしの最大値を更新して求められる
  • 長方形の区切り位置が i 列目と i + 1 列目の間にあるとしたときの2つの長方形の面積の最大値を r_{1} \le i, l_{1} \le r_{1}, l_{2} \ge i + 1, r_{2} \ge l_{2} の範囲での \mathrm{max}(S_{l_{1}, r_{1}}) + \mathrm{max}(S_{l_{2}, r_{2}}) で求める
  • 上記の計算を B を転置した場合でも求め、それぞれの最大値を比較する
    • 列ではなく行で区切る場合に対応

実装は

  1. H \times W の行列 B について以下の計算をする関数 f(B) を作成する
    • H \times (W + 1) の配列 C を用意し、 C_{i, j} を B_{i} の累積和 \sum_{j^{'} = 0}^{j - 1}B_{i, j^{'}}とする
    • W \times W の配列 S を用意する
    • 0 \le l \lt W, 0 \le r \lt W について、下記の処理を実施する
      • s_{0} = C_{0, r + 1} - C_{0, l}, s_{1} = 0 とする
      • h = 0, \dots, H - 1 について s_{1} = C_{h, r + 1} - C_{h, l} + \mathrm{max}(s_{1}, 0), s_{0} = \mathrm{max}(s_{1}, s_{0}) に更新する
      • S_{l, r} = s_{0} とする
    • 長さ W - 1 の配列 A を用意し、 L = S_{0, 0}, R = S_{W - 1, W - 1} とする
    • 0 \le r \lt W - 1 について下記の処理を実施する
      • 0 \le l \le r について、 L = \mathrm{max}(S_{l, r}, L), R = \mathrm{max}(S_{W - 1 - r, W - 1 - l}, R) と更新する
      • L を A_{r} に加算し、 R を A_{W - 1 - r} に加算する
    • \mathrm{max}(A) を返す
  2. B の転置行列 B^{T} を作成する
  3. \mathrm{max}(f(B), f(B^{T})) を出力する

計算量は O(HW(H + W))

公式解説

躓いた点

  • 列を固定する方法を思いつかなかった

4/24: DigitalArts プログラミングコンテスト2012 C - Chokutter

供養

問題

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

解法

  • ユーザ u がユーザ v を時刻 t_{i} にフォローし、時刻 t_{2} にアンフォローしたとすると、その間にユーザ u のタイムラインに表示されるユーザ v のつぶやきの数は (時刻 t_{2} におけるユーザ v のつぶやきの数) - (時刻 t_{1} におけるユーザ v のつぶやきの数) となる

実装は

  1. N + 1 個の連想配列からなる U を用意し、[1 \le i \le N] について U_{i, i} = \mathrm{true} とする
  2. 長さ N + 1 の配列 C, T を用意する
  3. s_{1}, \dot, s_{M} について以下の計算をする
    • s_{i} の先頭が t のとき、 C_{j} をインクリメントする
    • s_{i} の先頭が f のとき、 U_{j, k} = \mathrm{true}, U_{k, j} = \mathrm{true} とし、 C_{k} を T_{j} から、 C_{j} を T_{k} から減算する
    • s_{i} の先頭が u のとき、 U_{j, k} = \mathrm{false}, U_{k, j} = \mathrm{false} とし、 C_{k} を T_{j} に、 C_{j} を T_{k} に加算する
  4. 1 \le i \le N について U_{i} を見ていき、 U_{i, j} = \mathrm{true} なら C_{j} を T_{i} に加算する
  5. T を降順にソートし K 番目の要素を出力する

計算量は T の加減算が高々 O(M) なので、全体で O(N\mathrm{log}N + M)

公式解説

躓いた点

  • 愚直にシミュレーションしてTLE

4/25: 天下一プログラマーコンテスト2013予選B E - 天下一最短路コンテスト

供養

問題

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

解法

  • 点 1, 2, 3 と点群 A を考える
  • 正方形のある辺 e_{1} の中央に点 1、点1のある辺の対向の辺 2_{2} の両端付近に点 2, 3、 e_{2} の中心近辺に A が（可能な限り密集して）あるとする
  • 点 1 から最近傍を貪欲に辿ると 1 \to D \to 2 \to 3 となる
    • 2, 3 は逆の可能性もある
    • このときの移動距離は正方形の一片の長さを e、 D 内の移動を \alpha としておよそ \frac{5}{2}e + \alpha
  • 2番目の近傍を辿るとき、点2の位置をうまく調整すれば 1 \to 2 \to D \to 3 となる
    • D の最近傍点との距離よりは遠く、 D の中で2番目に近い点よりは近い位置をとる
    • このときの移動距離は正方形の一片の長さを e、 D 内の移動を \alpha^{'} としておよそ \frac{\sqrt{5} + 2}{2}e + \alpha^{'}
  • e \gg \alpha であれば、 \alpha^{'} が \alpha の2倍程度あっても誤差

実装は

  1. 100 を出力する
  2. (5000, 0), (0, 8649), (10000, 10000), (5000, 9990) を順に出力する
    • \sqrt{0^{2} + 9990^{2}} \lt \sqrt{5000^{2} + 8649^{2}} \lt \sqrt{0^{2} + 9991^{2}} となる
  3. 0 \le x \lt 12, 1 \le y \le 8 について、 (5000 + x, 9990 + y) を出力していく

計算量は O(1)

公式解説

躓いた点

  • 全く方針立たず

4/26: AtCoder Regular Contest 044 D - suffix array

供養

問題

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

解法

  • 元の文字列 S について A_{i} 文字目 s_{A_{i}} から始まる部分文字列を S_{A_{i}} とすると、 1 \le i \lt N について
    • S_{A_{i}} \lt S_{A_{i + 1}}
    • \iff s_{A_{i}} \lt s_{A_{i + 1}} \lor (s_{A_{i}} = s_{A_{i + 1}} \land S_{A_{i} + 1} \lt S_{A_{i + 1} + 1})
    • \iff S_{A_{i + 1} + 1} \lt S_{A_{i} + 1} ならば s_{A_{i}} \lt s_{A_{i + 1}}、そうでなければ s_{A_{i}} \le s_{A_{i + 1}}
  • s_{A_{1}} から貪欲に辞書順最小値を求めていくことができる

実装は

  1. 長さ N + 1 の配列 B を用意し、 0 \le i \lt N について B_{A_{i} - 1} = i + 1 とする
  2. 長さ N の配列 C を用意し、 1 \le i \lt N について B_{A_{i - 1} + 1} \lt B_{A_{i} + 1} ならば C_{i} = C_{i - 1}、そうでなければ C_{i} = C_{i - 1} + 1 とする
  3. \mathrm{max}(C) \ge 26 ならば -1 を出力して終了
  4. 0 \le i \lt N について、 s_{A_{i} - 1} が A の C_{i} 文字後 (e.g. 1文字後は B ) となるような文字列 S を作成し出力する

計算量は O(N)

公式解説

躓いた点

  • 英大文字だけで構築できない場合の処置を忘れていてWA

4/27: AtCoder Beginner Contest 164 E - Two Currencies

供養

問題

Difficulty: 1814 (記事作成時点)

解法

  • \mathrm{max}(A_{i}) \times (N - 1) 枚銀貨を持っていれば、それ以降換金なしで任意の点に到達できる
  • 点 i にいて銀貨を j 枚以上保有するための最短時間を \mathit{DP}_{i, j} としてDPをする
    • j の最大値は \mathrm{max}(A_{i}) \times (N - 1)
    • (現在時刻、現在地、銀貨の所有枚数) の組を要素として最も現在時刻が近いものから隣接点を探索してDP表を更新する

実装は

  1. L = \mathrm{max}(A_{i}) \times (N - 1) とする
  2. (N + 1) \times (L + 1) のDP表 \mathit{DP} を用意し、各要素を十分大きな数 \mathit{Inf} で初期化する
  3. Priority Queue \mathit{PQ} を用意し、 0 \le s \le S について、 (0, 1, s) を \mathit{PQ} にPushする
    • 各要素 (t, u, s) を比較して、最小の t を持つものをPopする
  4. \mathit{PQ} が空になるまで以下を繰り返す
    • \mathit{PQ} からPopし、 (t, u, s) とする
    • t \ge \mathit{DP}_{u, s} ならば何もせず次へ行く
    • \mathit{DP}_{u, s} = t とする
    • t + D_{u} \lt \mathit{DP}_{u, \mathrm{max}(s + C_{u}, L)} ならば (t + D_{u}, u, \mathrm{max}(s + C_{u}, L)) を \mathit{PQ} にPushする
    • u の各隣接点 v を接続する辺 i について、以下の処理をする
      • s \lt A_{i} ならば何もしない
      • t + B_{i} \lt \mathit{DP}_{v, s - A_{i}} ならば (t + B_{i}, v, s - A_{i}) を \mathit{PQ} にPushする
  5. 1 \le i \le N について \mathrm{max}(\mathit{DP}_{i, 0}) を出力する

計算量は A = \mathrm{max}(A_{i}) として O(ANM\mathrm{log}(AN))

公式解説

躓いた点

  • 上限の設定に失敗した

4/28: AtCoder Regular Contest 047 C - N!÷K番目の単語

供養

問題

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

解法

  • 0-indexで \frac{N!}{K} 番目の文字列 S の1文字目 s_{1} は利用可能な文字のうち \lfloor \frac{\frac{N!}{K}}{(N - 1)!} \rfloor = \lfloor \frac{N}{K} \rfloor 番目の文字となる
  • また、 s_{2} 以降は s_{1} で始まる文字列のうち \frac{N!}{K} - \lfloor \frac{N}{K} \rfloor \times K \times (N - 1)! = \frac{(N \% K) \times (N - 1)!}{K} 番目の文字列である
  • 一般化すると、 m_{0} = 1 としたときに s_{i} はその時点で使える文字のうち \frac{m_{i - 1} \times (N - i + 1)}{K} 番目の文字で、そのとき m_{i} = m_{i - 1} \times (N - i + 1) \% K となる
    • その時点で使える文字のうち j 番目の文字は、BITの二分探索などで求められる
  • 上記は0-indexの話なので、ここで求めた一つ手前の文字列が答えとなる

実装は

  1. 長さ N の配列 A を用意し、 m = 1 とする
  2. 0 \le i \lt N について A_{i} = \lfloor \frac{m \times (N - i)}{K} \rfloor とし、 m = m \times (N - i) \% K に更新する
  3. 0 \le i \lt N について以下の操作を実施する
    • A_{N - i - 1} = 0 ならば A_{N - i - 1} = i とする
    • A_{N - i - 1} \gt 0 ならば A_{N - i - 1} をデクリメントしてループを抜ける
  4. N 要素の累積和を取れるBIT B を用意する
    • \mathrm{Inc}(i) で i 番目の要素をインクリメントし、 \mathrm{Dec}(i) で i 番目の要をデクリメントするとする
    • \mathrm{Get}(i) で先頭から i 番目の要素までの累積和を取得する
  5. 1 \le i \le N について \mathrm{Inc}(i) を実施する
  6. 0 \le i \lt N について下記操作を実施する
    • \mathrm{Get}(s_{i}) \ge A_{i} + 1 となる最小の s_{i} を二分探索で求める
    • s_{i} を出力する
    • \mathrm{Dec}(s_{i}) を実施する

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

公式解説

躓いた点

  • 式の一般化ができなかった
  • 0-indexと1-indexの差分を吸収するのを忘れた

4/29: AtCoder Regular Contest 017 D - ARCたんクッキー

供養

問題

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

解法

  • \mathit{GCD}(A_{l}, \dots, A_{r}) = \mathit{GCD}(A_{l}, A_{l + 1} - A_{l}, \dots, A_{r} - A_{r - 1}) である
  • ある時点の A_{l} は入力時点での A_{1} との差分をBITで管理することで求められる
  • 差分のGCDはSegment Treeで求めることができる

実装は

  1. 長さ N + 2 の配列 D を用意し、 1 \le i \le N について D_{i + 1} = A_{i} - A_{i - 1} とする
    • A は0-indexで、 A_{N} = 0 とする
  2. N + 1 要素の計算ができるBIT \mathit{BIT} を用意する
    • \mathit{BIT.Update}(i, v) で i 番目の要素を v に更新する
    • \mathit{BIT.Get}(i) で先頭から i 番目の要素までの和を取得する
  3. N + 1 要素の計算ができるSegment Tree \mathit{ST} を用意する
    • \mathit{ST.Update}(i, v) で i 番目の要素を v に更新する
    • \mathit{ST.Get}(l, r) で \lbrack l, r) の範囲のGCDを取得する
  4. 1 \le i \le N + 1 について \mathit{BIT.Update}(i, D_{i}) および \mathit{ST.Update}(i - 1, D_{i}) を実施する
  5. 0 \le i \lt M について以下の操作を実施する
    • t_{i} \ne 0 のとき、以下の操作を実施する
      • t_{i} を D_{l_{i}} に加算する
      • \mathit{BIT.Update}(l_{i}, D_{l_{i}}) および \mathit{ST.Update}(l_{i} - 1, D_{l_{i}}) を実施する
      • t_{i} を D_{r_{i} + 1} から減算する
      • \mathit{BIT.Update}(r_{i} + 1, D_{r_{i} + 1}) および \mathit{ST.Update}(r_{i}, D_{r_{i} + 1}) を実施する
    • t_{i} = 0 のとき、 \mathit{GCD}(A_{0} + \mathit{BIT.Get}(l_{i}), \mathit{ST.Get}(l, r)) を出力する

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

公式解説

躓いた点

  • GCDを相対値で求める発想が無かった
  • A_{l} を A_{0} との差を使って求める発想が無かった
  • BITとSegment Treeのindexの整理で混乱した

4/30: AtCoder Regular Contest 015 C - 変わった単位

供養

問題

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

解法

  • 全点対探索で比率が最大化する組合せを求める
  • 最大単位と最小単位は整数比が保証されているが、それ以外は別に保証されていないことに注意

実装は

  1. 連想配列の連想配列 M を用意する
  2. 0 \le i \le N について、 M_{\mathit{large}_{i}, \mathit{small}_{i}} = m_{i}, M_{\mathit{small}_{i}, \mathit{large}_{i}} = \frac{1}{m_{i}} とする
  3. 配列 U を用意し、 R = 0 とする
  4. 各 \mathit{key}_{1} \in M について以下の操作を実施する
    • \mathit{k} \in M_{\mathit{key}_{1}} を U の末尾に追加する
    • U が空になるまで下記の操作を実施する
      • U の先頭要素を取り出し u とする
      • 各 v \in M_{u} について以下の操作を実施する
        • M_{\mathit{key}_{1}, v} が存在するなら何もせず次に行く
        • M_{\mathit{key}_{1}, v} が存在しなければ M_{\mathit{key}_{1}, v} = M_{\mathit{key}_{1}, u} \times M_{u, v} とし、 v を U の末尾に追加する
    • 各 \mathit{key}_{2} \in M_{\mathit{key}_{1}} について、 M_{\mathit{key}_{1}, \mathit{key}_{2}} \gt R ならば R = M_{\mathit{key}_{1}, \mathit{key}_{2}}, L = \mathit{key}_{1}, S = \mathit{key}_{2} とする
  5. L=RS を出力する

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

公式解説

躓いた点

  • 途中の比率が非整数になることの考慮忘れ
  • 浮動小数を整数に変換するときに何も考えずにキャストしたら誤差でWA