そのうち誰かの役に立つ

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

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

競技プログラミング AtCoder 平面幾何 DP

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

1/15: AtCoder Beginner Contest 151 F - Enclose All

供養

問題

Difficulty: 1698 (記事作成時点)

解法

最小包含円の半径を求める問題

  1. 互いに異なるある2点 p_{i}, p_{j} \in P について、それぞれから距離 r の円を描いたときの交点を考える
    • 2r \gt |p_{i}p_{j}| のとき、交点は2つ存在する
    • 2r = |p_{i}p_{j}| のとき、交点は1つ存在する
    • 2r \lt |p_{i}p_{j}| のとき、交点は存在しない
  2. 交点が存在したとき、その点を c とすると、 i = 1, \dots, N について |p_{i}c| \le r ならば P は半径 r の包含円を持つことが言える
  3. 任意の p_{i}, p_{j} の組み合わせにおいて上記の方法で半径 r の包含円が作れない場合、 P は半径 r の包含円を持っていない
    • 包含円の中心はいずれかの2点を結ぶ直線の垂直二等分線上に存在する
  4. r について二分探索して所定の誤差以下になるように近似解を求める

計算量はある距離 r の包含円が存在するかの判定に O(N^{3}) 、最小包含円としてありうる最大の大きさ（e.g. P の値域をすべて覆う大きさ）を R 、許容誤差を \delta としたときに二部探索で繰り返す回数は O(\mathrm{log}\frac{R}{\delta}) なので全体で O(N^{3}\mathrm{log}\frac{R}{\delta} )

公式解説

躓いた点

  • ライブラリとして持っていなかったので時間内に実装できなかった

1/16: AtCoder Grand Contest 029 C - Lexicographic constraints

供養

問題

Difficulty: 2096 (記事作成時点)

解法

使える文字種を固定したときに、条件を満たす文字列集合が構成できるかを判定して二部探索する

  1. 使える文字種を X とする
  2. L = \lbrack (l_{k}, s_{k}) \rbrack を考える
    • 初期値として (l_{0}, s_{0}) = (0, 0) を持っているとする
    • 1 \le k において (l_{k}, s_{k}) は L が表現する文字列の s_{k - 1} + 1 文字目から s_{k} 文字目までを文字種 l_{k} で構成することを意味する
      e.g. L = \lbrack (0, 0), (1, 3), (3, 4), (1, 6) \rbrack で表現される文字列は文字種1を a 、文字種3を c として aaacaa となる
    • 以降、表記の簡略化のため (l_{len(L) - 1}, s_{len(L) - 1}) を (l_{-1}, s_{-1}) と表す
  3. i = 1, \dots, N について、辞書順で S_{i - 1} \lt S_{i} かつ辞書順最小の S_{i} を作るため以下のように L を操作する
    • a_{i} \gt s_{-1} のとき
      • (a_{i}, 1) を追加する
        • S_{i} は S_{i - 1} に a_{i - 1} + 1 文字目から a_{i} 文字目まで文字種1を追加したものである
    • a_{i} \le s_{-1} のとき
      • a_{i} \le s_{j} である最小の j を探す
      • s_{j} を a_{i} に更新する
      • (l _{j}, s_{j}) より後ろの要素を削除する
        • S_{i - 1} を a_{i} 文字まで削ることを意味する
      • 1 \le k, l_{k} \lt X である最大の k を探す
      • (l_{k}, s_{k}) の直後に (l_{k} + 1, s_{k}) を挿入し、 (l_{k}, s_{k}) を (l_{k}, s_{k} - 1) に更新する
        • s_{k} - 1 = s_{k - 1} である場合、 (l_{k}, s_{k}) を削除する
        • （インクリメント可能な） s_{k} 文字目をインクリメントすることを意味する
      • s_{k} \lt a_{i} ならば (l_{k} + 1, s_{k}) より後ろの要素を削除し、 (a_{i}, 1) を追加する
        • 辞書順最小にするため
  4. 上記の方法で最後まで L を更新できる最小の X を二分探索し出力する

計算量は各文字列を作れるかの判定が O(\mathrm{log}N)、値を固定したときに判定を O(N) 回実施し、文字種は N 以下であることを保証できるので全体で O(N\mathrm{log}N)

公式解説

躓いた点

  • 二部探索しなくても一発で最適化できると思っていたらWA

1/17: AtCoder Regular Contest 081 E - Don't Be a Subsequence

供養

問題

Difficulty: 2098 (記事作成時点)

解法

  • A = s_{0, 1}, \dots, s_{0, k_{0}}, s_{1, 1}, \dots, s_{1, k_{1}}, \dots, s_{j, k_{j}} と考える
    • このとき、 1 \ge j について s_{j, 1}, \dots, s_{j, k_{j}} は a から z までをすべて含む最短の連続部分文字列である
    • s_{0, 1}, \dots, s_{0, k_{0}} には a から z で少なくとも1つ存在しない文字がある
  • 上記のとき、 A の部分文字列に存在しない文字列の長さの最小値は j + 1 である
    • j 以下の場合、その文字列の i 文字目を s_{i, 1}, \dots, s_{i, k_{i}} から選べば構成できる
    • s_{0, 1}, \dots, s_{0, k_{0}} に存在しない文字を s^{'}_{0}、 1 \le i \le j について s^{'}_{i} = s_{i, 1} として構成される S^{'} は A の部分文字列として存在しない
      • s^{'}_{0} は s_{1, 1}, \dots, s_{j, k_{1}} から選ばなければならず、 s_{i, 1}, \dots, s_{i, k_{i}} に s^{'}_{i} と同じ文字は s_{i, 1} しか存在しないため、 s^{i} は s_{i + 1, 1}, \dots, s_{i + 1, k_{i + 1}} から選ばざるを得ないため、 s^{'}_{j} を選ぶことができない

辞書順最小の文字を選ぶためには

  1. A = s_{0, 1}, \dots, s_{0, k_{0}}, s_{1, 1}, \dots, s_{1, k_{1}}, \dots, s_{j, k_{j}} としたとき、 B = \lbrack b_{i} \mid b_{0} = 0, b_{i} = j\; s.t.\; a_{j} \in s_{j, 1}, \dots, s_{j, k_{j}} \rbrack を作る
    • A を後ろから見ていって全ての文字種が登場したところでインクリメントし、前から累積和を取っていけば b_{j} が構成できる
  2. p_{0} = 0 とする
  3. 0 \le i \le j について p_{i} 文字目より後ろで最初に文字 s が出てくる位置を P(p_{i}, s) としたとき、 b_{p_{i}} \lt b_{P(p_{i}, s)} であるような辞書順最小の文字を s^{'}_{i} とし、 p_{i + 1} = P(p_{i}, s^{'}_{i}) と決めていく
    • 文字種ごとに登場位置を配列で覚えておけば二分探索で求められる
  4. a_{p_{j + 1} + 1}, \dots, a_{N} に存在しない文字で辞書順最小の文字を s^{'}_{j + 1} とする
  5. s^{'}_{0}, \dots, s^{'}_{j + 1} を出力する

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

公式解説

躓いた点

  • suffixを作る発想がなく、 i 文字目で存在しうる最短・辞書順最小の部分文字列を求めていてWA

1/18: AtCoder Regular Contest 100 E - Or Plus Max

供養

問題

Difficulty: 2102 (記事作成時点)

解法

  • i\; \mathrm{OR}\; j = j であるような関係を i \subseteq j と表記する
    • i, j をbitで表現したときに立っているbitの集合についての包含関係となる
  • i = 1, \dots, 2^{N} - 1 について、 B_{i} = \lbrace a_{j} \mid j \subseteq i \rbrace を考える
    • 各 B_{i} の上位2要素の和で累積最大値を作っていけばよい
  • i = 0, \dots, 2^{N} - 1 について、 i \subseteq x であるような B_{x} で上位2つに入るか比較されればよい
    • 0 \le j \lt N について、 k = i\; \mathrm{OR}\; 2^{j} を考え、 B_{k} についてだけ考える
      • x \subseteq y \subseteq z のとき、 x \subseteq z は y \subseteq z のときにまとめて計算できるので、 最小の差( y \setminus x = 1)である x \subseteq y だけ考えればよい
      • このようなテクニックを集合に関するゼータ変換とか呼ぶらしい

実装では

  1. i = 0, \dots, 2^{N} - 1 について、 B \lbrack i \rbrack = \lbrack \lbrack a_{i}, i \rbrack, \lbrack 0, -1 \rbrack \rbrack とする
    • 以降、表記の簡略化のため B \lbrack i \rbrack \lbrack j \rbrack \lbrack k \rbrack を b_{i, j, k} のように表記する
  2. i = 0, \dots, 2^{N} - 1 について、 b_{i} を用いて次のように更新していく
    • j = 0, \dots, N - 1 について、 k = i\; \mathrm{OR}\; 2^{j} とする
    • b_{k, 0, 0} \lt b_{i, 0, 0} ならば、 b_{k} = \lbrack b_{i, 0}, b_{k, 0} \rbrack とする
    • そうでないとき、 b_{k, 1, 0} \lt b_{i, 0, 0} \land b_{k, 0, 1} \neq b_{i, 0, 1} ならば、 b_{k} = \lbrack b_{k, 0}, b_{i, 0} \rbrack とする
      • 状況によっては同じ要素を2回以上評価してしまうため
    • 上記の更新後、 b_{k, 1, 0} \lt b_{i, 1, 0} ならば b_{k} = \lbrack b_{k, 0}, b_{i, 1} \rbrack とする
  3. c_{0} = 0 とし、 i = 1, \dots, 2^{N} - 1 について、 c_{i} = \mathrm{max}(b_{i, 0, 0} + b_{i, 1, 0}, c_{i - 1}) を出力していく

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

公式解説

躓いた点

  • ゼータ変換を知らず愚直に B_{i} を作ろうとして O(2^{2N}) のアルゴリズムにしてしまいTLE

1/19: AtCoder Regular Contest 067 E - Grouping

供養

問題

Difficulty: 2122 (記事作成時点)

解法

  1. \mathrm{DP} \lbrack 0 \rbrack \lbrack 0 \rbrack = 1 で初期化する
  2. i = 1, \dots, B - A + 1 について、 \mathit{DP} \lbrack i \rbrack \lbrack j \rbrack は x = A - 1 + i 人までのグループに属する人の合計が j 人であるとする
  3. i = 1, \dots, B - A + 1, j = 0, \dots, j について、 \mathit{DP} \lbrack i \rbrack \lbrack j \rbrack = \mathit{DP} \lbrack i - 1 \rbrack \lbrack j \rbrack + \sum_{C \le k \le D}\mathit{DP} \lbrack i - 1 \rbrack \lbrack j - x * k \rbrack \times \frac{_{j}\mathrm{P}_{j - x * k}}{(x!)^{k}k!} が言えるので、 i = 1, \dots, B - A + 1, j = 0, \dots, j, k = 0, C, \dots, D について、 y = j + x * k とし、 \mathit{DP} \lbrack i \rbrack \lbrack y \rbrack = \mathit{DP} \lbrack i \rbrack \lbrack y \rbrack + \mathit{DP} \lbrack i - 1 \rbrack \lbrack j \rbrack \times _{y}\mathrm{P}_{j} \times (x!)^{-k} \times k!^{-1} と更新していく
    • j 人でのあるグループ分けについて x 人グループを k 個追加したときに、グループを個別に認識した組合せ数の変化分が \frac{_{j + x * k}\mathrm{P}_{j}}{(x!)^{k}}
    • ある2人が x 人グループの g_{x, 1}, g_{x, 2} のどちらかに所属しているとき、グループを個別に認識している組合せだと (g_{x, 1}, g_{x, 1}), (g_{x, 1}, g_{x, 2}), (g_{x, 2}, g_{x, 1}), (g_{x, 2}, g_{x, 2}) はそれぞれ別として認識されるが、問題のカウント方法だと (g_{x, 1}, g_{x, 1}) と (g_{x, 2}, g_{x, 2}) 、 (g_{x, 1}, g_{x, 2}) と (g_{x, 2}, g_{x, 1}) はそれぞれ同一視されるので、その差分を解消するために k!^{-1} をかける
  4. \mathit{DP} \lbrack B - A + 1 \rbrack \lbrack N \rbrack を出力する

計算量は 0 \le j + x * k \le N となるよう適切に枝刈りすれば1マスあたりの更新が \frac{N}{x} 回に抑えられるので、合計で O(N^{2}\mathrm{log}N)

公式解説

躓いた点

  • 題意を満たす集合をはじめに作ろうとしてしまいTLE
  • 正確に計算量の見積もりができず O(N^{3}) と思っていた

1/20: キーエンス プログラミング コンテスト 2020 E - Bichromization

供養

問題

Difficulty: 2291 (記事作成時点)

解法

  • ある頂点 u について、 u の任意の隣接点 v について D_{u} \lt D_{v} であるとき、 u と異なる色で u から最小コストで到達できる点を v^{'} とすると、そのときの経路 u \to v^{'} で通る u の隣接点 v がどちらの色であったとしても D_{u} \lt D_{v} と矛盾するので、そのときは条件を満たす割り当ては作成できない
  • 各頂点 u について、 u の隣接点のうち D_{v} \le D_{u} であるような点 v を選び、辺 (u, v) の重みを D_{u}、 u と v を異なる色になるように彩色すれば、題意を満たす経路を確保できる
    • D_{u} = D_{v} = D_{w} のときに u, v, w がそれぞれ v, w, u を隣接点として選ぶと w \to u は同色なので題意を満たす経路ではないが、 w \to v が題意を満たす経路であるので w は隣接点として v を選べばよい

実装では

  1. G の部分グラフ H を V(H) = V(G), E(H) = \emptyset で初期化する
  2. 1 \le u \le N について、 u の隣接点集合の各点 v を見て以下の操作を実施する
    • D_{v} \le D_{u} である点を1つ選ぶ
      • 隣接点の頂点番号順に見ていって最初に表れたものとする
    • \lbrace U_{i}, V_{i} \rbrace = \lbrace u, v \rbrace であるような辺 i の重みを D_{u} とする
    • 辺 i を H に追加する
    • D_{v} \le D_{u} であるような点が1つもなければ -1 を出力して終了
  3. H をもとに頂点の彩色を決めていく
    • 1 \le u \le N について、まだ彩色が決まっていない場合適当に決める
      e.g. B 固定
    • u を起点に H を深さ優先探索し、隣接点は異なる色になるように彩色を割り当てていく
  4. 1 \le i \le M について、辺 i の重みが決まっていなければ 10^{9} にする
    • 最短経路選択の邪魔をしない大きさにする
  5. 彩色及び各辺の重みを出力する

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

公式解説

躓いた点

  • 問題に取り組み始めた時点で残り時間が無かった
  • D_{u}, D_{v} の大小関係と解の関係に思い至らなかった

1/21: AtCoder Beginner Contest 152 E - Flatten

供養

問題

Difficulty: 1383 (記事作成時点)

解法

LCMを作ってそれぞれの値で割って足すだけだが、LCMが巨大になりそうなときにどうやって保持するかという問題

  1. i = 1, \dots, N について a_{i} を素因数分解し a_{i} = p_{1}^{k_{i, 1}} \dots p_{l}^{k_{i, l}} とする
  2. 素因数をkey、登場回数をvalueとしたhashmapを作成し、それらを合成してLCMを作る
    • a_{i}, a_{j} の素因数集合を P_{i, j} としたとき、それぞれ登場回数の多い方を採用するとLCMの素因数分解と同等となる
      i.e. \mathit{LCM}(a_{i}, a_{j}) = \prod_{p_{l} \in P_{i, j}}p_{l}^{\mathrm{max}(k_{i, l}, k_{j, l})}
  3. LCM mod 10^{9} + 7 を作成し、 \sum_{1 \le i \le N}\mathit{LCM} \times a_{i}^{-1} を出力する

計算量は \mathrm{max} \lbrace a_{i} \rbrace = A として O(N\sqrt{A} + A)

公式解説

躓いた点

  • 効率よくLCMを保持する方法を思いつくのに時間がかかった