AtCoder Regular Contest 093
Updated:
今回は解説 PDF が出ないのでしょうか？ E までは解説を書いてみましょう。 F は包除原理でしょうから、少し考えて、無理だったら解説放送を見ます。 → (03/27) PDF 出ました。解説放送や PDF を見る前に F が解けました。
Source codes
Solutions
C - Traveling Plan
$a_0 = a_{N+1} = 0$ とする。まず普通に $S = \sum_{i = 0}^{N} \lvert a_i - a_{i+1} \rvert$ を求めておく。答えは $S - \lvert a_{i-1} - a_i \rvert - \lvert a_i - a_{i+1} \rvert + \lvert a_{i-1} - a_{i+1} \rvert$ でそれぞれ $O(1)$ で求まる。
D - Grid Components
まず $100 \times 100$ のグリッドを用意する。上半分を黒く塗り、下半分を白く塗る。 この時点で連結成分は $1$ 個ずつ。あとは $(2i + 1, 2j + 1)$ を白く塗って、 $(2i+1 + 50, j+1)$ を黒く塗って $(A, B)$ を達成する。
ポイント
昔 Code Formula 2014 Final F - 100個の円 の解説で chokudai さんが「こういう問題はまずどのくらい余裕があるのかを概算してみましょう」と言っていたのを思い出していた。余裕があれば解法は大雑把で良いからだと。
この問題だと市松模様に塗ることで $A = B = 5000$ が達成できる。これに比べれば $A, B \leq 500$ は十分過ぎるくらい余裕があることがわかるだろう。そうしてこの解答にたどり着くことができた。
E - Bichrome Spanning Tree
解法
まず最小全域木をクラスカル法で求める。この時、使わなかった辺を $W$ に収納し、使った辺で木 $T$ を作成する。 $T$ のコストを $Y$ とする。 $X < Y$ のとき、答えは $0$ である。以下 $X \geq Y$ とする。 $W$ の辺の数を $L$ とする。 $K = N-1$ が $T$ の辺の数である。 $T$ は $0$ を根とする(別にどれでもいいけど)。
まず $X = Y$ の場合を考察する。この場合 $T$ の辺を白と黒の両方を使って塗る場合の数は $2^K - 2$ である。この場合 $W$ の辺の彩色については何ら制約がないので、「すべての辺の塗り方であって、$T$ の辺を白と黒の両方を使って塗る場合の数」は $2^L (2^K - 2)$ 通りである。
次に、「$X = Y$ の場合であって、$T$ の辺を白と黒の片方だけで塗る」場合と「$X > Y$」の場合を考察する。後者の場合、 $T$ の辺は 白と黒の片方だけで塗る必要がある 。説明の都合上、黒く塗ることにする。最終的な答えを $2$ 倍する。この場合、 $W$ の辺の塗り方によって、問題文の条件を充たすかどうかが決まる。 $e = (c, u, v) \in W$ とする。ここで $c$ はコスト、 $u, v$ は端点である。 $\mathrm{lca}(u, v)$ で $u, v$ の最小共通祖先を表すものとする。
仮に白色の $e$ を $T$ に追加して、その中で最小全域木を作ることにすると、何を削除することになるだろうか？ 答えは、$u, \mathrm{lca}(u,v), v$ をつなぐ道上の辺の最大コストの辺を削除することになる。このことを念頭に置いて、「$u, \mathrm{lca}(u,v), v$ をつなぐ道上の辺の最大コスト」を $c’$ と表記することにする。クラスカル法のアルゴリズムより、 $c \geq c’$ が成立する。
- $c - c’ < Y - X$ のとき、もし $e$ を白く塗ると、コスト $X + c - c’ < Y$ の全域木ができる。これは阻止しなければならない。よってこのような辺は黒く塗るしかない。このような辺の数を $L_1$ と書く。
- $c - c’ = Y - X$ のとき、もし $e$ を白く塗ると、コスト $X + c - c’ = Y$ の全域木ができる。これは必要である。よってこのような辺のうちどれか $1$ つは白く塗るしかない。このような辺の数を $L_2$ と書く。
- $c - c’ > Y - X$ のとき、もし $e$ を白く塗ると、コスト $X + c - c’ > Y$ の全域木ができる。これは必要はないが、阻止する必要もない。よってこのような辺は黒く塗っても白く塗っても構わない。
以上より、「すべての辺の塗り方であって、$T$ の辺を白と黒のいずれか片方を使って塗る場合の数」は $2(2^{L-L_1} - 2^{L-L_1-L_2})$ である。
実装の問題点
クラスカル法は Union-Find を用いることに注意。
問題は「$u, \mathrm{lca}(u,v), v$ をつなぐ道上の辺の最大コスト」をいかに早く計算するかである。 LCA を高速に計算する際にダブリングを用いる。詳しくはプログラミングコンテストチャレンジブック p.293 を見て欲しい。本では LCA だけ管理しているが、 ダブリングを更新する際に LCA と同時に「道中の最大コスト」を持って更新していけばよろしい 。詳しくはソースコードを見て欲しい。 117 行目からの dfs, init2, LCA がそれである。
計算量
クラスカル法は $O(M \alpha(N))$ である。 LCA のダブリングは $O(N \log N)$ である。 $L = O(M)$ 本の「クエリ」に答えるのには $O(\log N)$ で済む。よって全体の計算量は $O(M \alpha(N) + N \log N + M \log N) = O(M \log N)$ 程度である。 $N \leq 1000$, $M \leq 2000$ なので十分間に合う。この制約だと、多分想定解法はもっと時間かかっても大丈夫なものなのかもしれない。例えば LCA をダブリングなしで素朴に求めても AC される可能性がある。
ポイント
「白と黒の片方だけで塗る必要がある」はすぐに思いついた。 LCA が問題になるのはわかったが、ダブリングに最大値を持たせるのは Code Thanks Festival 2017 H - Union Sets の解説で学習済みだったので思いつくことができた。すべての考察が終わってから書き始めた。実装時間は 40 分程度あったようだ。残り時間 4 分程度で書き終えたが、サンプルが通らずにそのままタイムアップ。間違えていた点はこことここにあるように、 $u, v$ を更新した後に最大コストを更新したことである。ここだけミスらなければ一発で通っていただけに、残念である。
変数を更新する前に、各パラメータを更新しましょう という普通の反省点に尽きてしまう。
別解
上の解法は私がコンテスト中に試みた解法である。それとほぼ同じ解法、ほぼ同じ実装になるものの、解説放送で rng さんが示してくれた方針がとても明快だと思ったので、別解という形でメモしておきたいと思う。
関数 $f \colon \mathbb{N} \to \mathbb{N}$ を
$f(n) =$ コスト $n$ 以下の全域木を作ろうとしても、そもそも構成できないか、または、そいつを構成する辺が全部同じ色で塗られているがゆえに作れないような、全部の辺を塗る場合の数
と定める。$f$ は減少関数である。すると答えは $f(X-1) - f(X)$ である。
次に、関数 $g \colon E \to \mathbb{N}$ を
$g(e) = e$ を使ってできる全域木のうち、最小のコスト
と定める。 $e$ は以下のように求まる。まずクラスカル法で最小全域木 $T$ を求める。それを構成する辺 $e$ に対し $g(e)$ は最小全域木 $T$ のコスト $Y$ である。次にクラスカル法で採用しなかった辺 $e = (c, u, v) \in W$ に対し、「$u, \mathrm{lca}(u,v), v$ をつなぐ道上の辺の最大コスト」を $c’$ と表記することにすると、 $g(e) = c - c’ + Y$ である。
以上で求まった $g$ を用いて $f$ を計算することができる。
\[ f(n) =
\begin{cases}
2^{M - C + 1} & (C > 0), \\
2^{M} & (C = 0).
\end{cases}
\]
ここで $C = \sharp \{ e \in E \mid g(e) \leq n \}$ とした。
実装では、まず multiset では $C$ がもとまらないことに気づいた。次に二分探索で $C$ を求めるところを間違えた。この場合 sort 済みの vector<ll> S を用いるが、 S[0] > n の際に事前に場合分けをすることになる。
F - Dark Horse
規約と定義
これから取り扱うあらゆる添字は全て 0-indexed とする。
$n \in \mathbb{N}$ とする。 レベル $n$ のトーナメント とは、 $2^n$ 人が対戦するトーナメントを指す。
プレイヤー $0$ を 主人公 と呼ぶ。他のプレイヤーは 選手 と呼ぶ。
順列がひとつ決まると、そこから勝敗が決まる旨が問題文に書かれているが、競技の順序を変更して以下のように進行する。すなわち、まず選手たちだけが戦い勝敗を決定する。あとは主人公 VS 選手を $N$ 戦残すのみとなるまで競技を進行し、そこから主人公 VS 選手の戦いをする。つまりパラマス方式のトーナメントの最下位の状態から主人公が優勝するかどうかを判定する。このパラマス方式のトーナメントを 本戦 と呼ぶことにする。選手たちは $i = 0, \dots, N-1$ に対し レベル $i$ の小トーナメント を実行し、その優勝者が主人公と本戦で $i$ 回戦を戦うことになる。主人公が敗北しても本戦は便宜上主人公が上がって続行し、一度も敗北がなかった場合に優勝と判定することにする。
自明な同一視を 2 つする
この問題では順列でトーナメントを区別しているが、順列では区別できても対戦相手が全く同じトーナメントというものが存在する。例えば $N = 1$ の順列で、 $(0, 1)$ と $(1, 0)$ は対戦相手が全く同じなので全く同じトーナメントと言える。この同一視は、 $2^{2^N - 1}$ 通りをまとめることができる。
次に、小トーナメントを優勝者を考察する。レベル $i$ の小トーナメントに参加する選手を $2^i$ 人選んだ時点で、どのようにトーナメント表を組もうとも、優勝者は変わらない。選んだ選手の中で一番若い番号の選手が最強で優勝することになるからだ。この問題で大事なのは本戦に出場する選手であるので、小トーナメントに出場する選手が同じであれば、トーナメント表の組み方が異なるものも同一視することにする。レベル $i$ の小トーナメントで、小トーナメントに出場する選手が確定した段階で、先ほどの同一視でなおも同一視できないトーナメントの組み方を $L[i]$ とする。実験してみる。 $L[0] = L[1] = 1$ は明らか。 $L[2]$ を考察しよう。出場する選手の集合を $\{ 1, 2, 3, 4 \}$ とする。この場合、 $1$ と初戦で対戦する選手の場合の数が問題である。 $L[2] = 3$ である。 $L[4]$ の場合は、出場する選手を $\{ 1, \dots, 8 \}$ とする。トーナメント表の一番左に $1$ を入れるとする。 $1$ の対戦相手の場合の数は $\begin{pmatrix} 7 \\ 1 \end{pmatrix}$ である。次にそのとなり $2$ つを選ぶ場合の数は $\begin{pmatrix} 6 \\ 2 \end{pmatrix}$ である。隣 $4$ つはレベル $2$ の小トーナメントになっているので、 $L[2] = 3$ 通りある。ここまでくると一般化ができる。
\[ L[i] = \prod_{j = 0}^{i-1} \begin{pmatrix} 2^i - 2^j \\ 2^j \end{pmatrix} L[j] \]
で順次求まる。
以下では、以上の状態は全て同一視されるものとする。
包除原理
主人公が優勝するための必要十分条件は、本戦で $A_i$ たちと当たらないことである。 $\mathbb{A} = \{ A_0, \dots, A_{M-1} \}$ とおく。そこで、 $S \subset N = \{ 0, \dots, N-1 \}$ に対し、
$DP[S] = $ 全ての $i \in S$ に対し、本戦 $i$ 回戦の主人公の相手が $\mathbb{A}$ の元である場合の数
と定める。すると包除原理より、答えは
\[ X = \left( 2^{ 2^{N}-1} \prod_{i = 0}^{N-1} L[i] \right)\sum_{S \subset N} (-1)^{\lvert S \rvert} DP[S] \]
であることになる。そして $DP[S]$ を DP で求めることにする。
DP を思いつくまでと DP の遷移
さて、普通の思考過程だと、これを思いついた段階で DP の仕方もわかっているはずである。少し議論を戻すことにする。つまり $DP[S]$ はすでに色々な状態を区別していないでひとまとめになっている。前節の議論までした段階だと、素朴には「本戦 $i$ 回戦の主人公の相手が $\mathbb{A}$ の元である」ではなくて「本戦 $i$ 回戦の主人公の相手の番号も決めないと場合の数が変わってくる」ことが念頭にあるはずである。ではどのように場合の数を求めるのか、後者の設定で思考する。
まず主人公が本戦で当たる勝てない相手を決める。勝てない相手を決めた後、その子らが何回戦で主人公と当たるかを決める。次に、その子らを優勝させるような各レベルのトーナメントを作ることになる。ここで、レベル $i$ の小トーナメントで $A_j$ を優勝させたければ、 $A_j$ より大きな番号を持った選手のうち、今まで選ばれていない選手を $2^i - 1$ 人選んでくることになる。そして「今まで選ばれていない選手」の管理を容易にするためには、 $A_j$ の数字が大きい順番に決定していけば煩雑でないことがわかる。大きい方から決定していくことにより、「今まで選ばれた選手」は「$A_j$ より大きな番号を持った選手」であるから迷うことなく選べることになる。そうして決まっていた「本戦で当たる勝てない相手」以外の小トーナメントに出場する選手を限界まで選んでいく。つまり $N$ 個の組合せ数を掛け算したものが、この場合の場合の数となる。ここに足し算が含まれていないから、項をまとめて DP で遷移できる可能性があることに気づく。
ここでしかできないので流れをぶった切って補足：仮に $i \subset N$ を bit で「構築し終えた小トーナメントのレベルたち」とすると、「今まで選ばれた選手」の数はちょうど $i$ である(小トーナメントの優勝者も含めて)。
ここからどうやって次のことを思いついたのかもはや忘れてしまったのだが(記事の末尾に思いついた時のシチュエーションはメモしておく)、ここで注目するべきポイントは、以下の 3 つ。
- $A_j$ の数字が大きい順番に決定していく。
- その上で「今まで選ばれた選手が何人であるか」が一致していれば、「$A_j$ を優勝させるレベル $i$ のトーナメント」の作り方は、どの人が今まで決めた小トーナメントの優勝者であろうと同じ場合の数である。
- 最後まで埋まらなかった小トーナメントの作り方の場合の数は、埋まった小トーナメントのレベルが一致していれば、どの人が小トーナメントの優勝者であろうと同じである。
これらを反映すると、 $DP[S]$ に場合の数を記録しながら、以下のように遷移し最終結果を得ることができる。初期状態： $DP[0] = 1$ 、他は $0$ 。遷移：まず $k = M-1, \dots, 0$ に対し、 $i \subset N$ (大きい順) に対し、 $0 \leq j \leq N-1$ に対し、 $j \not\in i$ ならば \[ DP[i \cup \{ j \} ] += \begin{pmatrix} 2^N - 1 - A_k - i \\ 2^j - 1 \end{pmatrix} DP[i] \] を実行する。 $k$ のループが終わった段階で、 2. まで終わっている。あとは 3. である。全ての $i \subset N$ に対し、$0 \leq j \leq N-1$ に対し、 $j \not\in i$ ならば、 \[ DP[i] *= \begin{pmatrix} R \\ 2^j \end{pmatrix} \] とする。ここで $R$ は小トーナメント割当先が決まっていない選手の残り人数で $j$ を回すたびに更新する。
以上で $DP[S]$ が正常にもとまったので、 $X$ が求まる。計算量はループを素直に数えればわかる通り、 $O(M \cdot 2^N \cdot N + 2^N \cdot N) = O(2^N MN)$ である。 $N, M \leq 16$ ならちょうど間に合うくらいだろうか。
ポイント
基本的には上記をそのまま実装するとよろしいが、工夫できる点がある。それは $DP[i] = 0$ の際に遷移をしないということである。これは『数え上げテクニック集』に書かれている。
配る DP を考えます。このとき、DP 配列の見ている場所の値が 0 なら遷移をしない、という単純な枝刈りが、しばしば (特に高次元の DP における) 定数倍高速化において威力を発揮します。
問題によっては、あるパラメータの値によって他のパラメータの値が大きく制約を受けることがあります。制約条件を求め、ループを回す範囲を手動で決定しても良いのですが、単に「0 通りなら遷移しない」という一文を書くだけで、詳細を詰めることなしに定数倍高速化をすることができます。
ーー DEGwer 氏 『数え上げテクニック集』 11.7 簡単な枝刈り
間違えた箇所：入力を A[i]--; としていなかった。 $R$ の定義する位置をループの内側にしてしまった。
Others
E が時間内に AC もらえなかったのは残念だったが、最高レートを更新した。
F はなんとなく包除原理だなと思っていたが、当然コンテスト中にはやる時間はなかった。具体的に $DP[S]$ でいいじゃんと思いついたのは『citrus』をネットフリックスで見ていた時だった。どうせこんな記事を最後まで見ている読者はいないだろうから正直にぶっちゃけることにすると、 5 話を見ている間に $L[i]$ の漸化式がわかった。 6 話の末尾で柚子と芽衣が濃厚なキスをしているときに考えがだんだんまとまってきて、あ、この遷移で解ける…とわかったのである。私が尊敬するエンジニア(後輩、同級生とわず)で百合が好きな人がいるのだけど、どうしてこうも優秀な人は百合が好きなのだろうと昔から不思議に思っていた。今回なんとなく理解することができた。つまり、百合は文法が決まっているから、脳のリソースに余裕を持たせてくれる。例えば 6 話なんてのはめちゃくちゃ典型的な百合作品の展開だと思う。疎遠で意思疎通が取れにくかった父親と誤解が解ける。基本的には血縁男性キャラと不仲で終わる濃厚系百合は少ないから最初の時点で既定路線。一件落着、その結果気分が乗ってきてパートナーの百合相手と濃厚なキスをする。こんなキスはしたことない…！ みたいな。超典型なので、過去のアニメ視聴の経験に照らし合わせて何も考えずに見ることができるのだ。その結果脳裏で演算されている数学や計算機の構造をなんとなく考えることができて、思わぬ進捗をもたらすという…多分こういうことだと思う。
読者はこれを見てなんというこじつけだろうと思うかもしれないが、私はふざけているわけではない。例えば『ダーリン・イン・ザ・フランキス』を見ているときに同じことが起こりそうか真剣に考えて見て欲しい。ダリフラは複雑なロボットアニメ要素は低いけれども、「子供たち」「大人たち」の世界の構造自体が謎に包まれているし、思春期をある意味真正面から描いている作品だから、集中して見ないと理解ができないアニメだと思う。百合好きで優秀なエンジニアの中には男女の恋愛モノを嫌悪する人もいるが、その理由は、彼らが求めている快楽は百合でしか味わえないからというのもあるのかもしれないが、消費リソースが桁違いだからというのも一説として挙げられよう。
正直にいうと F は、解説を見ずに自力で最後まで解けるとは思っていなかった。彷徨うような思考をずっと続けてしまうのだろうと思っていた。それでも自分で十分考えてから解説放送を見ようと思っていた。結果的に自力で解けたのは嬉しいことである。コンテスト最高レートを更新することよりも、次につながることだと思う。
解説 PDF をざっと読んだ。 E は同じ方針と言って差し支えなかろう。ただし $(u, \mathrm{lca}(u, v), v)$ 上のパスの最大値を求める部分は素朴にやることを想定しているようである。 F は、根本の考え方は同じだが、ほぼ違う方針と言って差し支えないかと思う。解説放送も見た。こちらは E の方針が明快で非常に参考になった。ので、追記した。