AtCoder Grand Contest 043 C - Giant Graph

お題箱より。

この問題は数ヶ月前に「なぜこの発想を思いつけるのか分からない」というリクエストをもらっていて、私にも分からなかったので記事を書けずにいました。でしたが、（同じ人が違う人かは分かりませんが）2つ目のリクエストをもらったので、自分なりに解説をしていこうと思います。

解法

最適解の構造を考える

頂点 $(x, y, z)$ について、 $x+y+z$ の値を「レベル」と呼ぶことにします。

レベルが $1$ 増えると重みが $10^{18}$ 倍になるため、「レベル $k$ である頂点を $1$ つ取るほうが、レベル $k-1$ 以下である頂点全てを取るよりも得である」ということが成立します。さらにグラフの作り方からレベルが等しい頂点間に辺はないので、レベルの大きい方から貪欲に頂点を選んでいくことで最適解を求めることができます。

よって最適解を求める（遅い）アルゴリズムとして、以下のようなものが考えられます。

全ての頂点に何も書かれていない状態から始める。全ての頂点に印が付けられるまで以下を繰り返す。
- 今残っている頂点の中で最もレベルの高い頂点を1つ選び、それに○印を書く（選ぶ頂点として採用する）。それに接続している頂点全てに×印を書く。

※3次元の図示が大変なので2次元で描いています…

f:id:betrue12:20200702190353p:plain

ゲーム問題との類似

ここで最も重要な気づきは、この最適解を求めるアルゴリズムがゲーム問題における後退解析と同じ手順になっている、という点です。

後退解析とは、交互に手番を取るタイプの2人ゲームで

ゲームのルールで「この状態で手番が回ってきたら負け」と指定されている状態は負け状態とする。
負け状態に遷移可能、つまり相手に負けを押し付けられる状態は勝ち状態とする。
勝ち状態にしか遷移できない状態は負け状態とする。

という手順で、最終状態から遡るように各状態の勝ち負けを決めていくものです。（俗にWL-Algorithm等とも呼ばれているようです）

本問題のグラフにおいて、2人ゲームを

1つの頂点に駒を置いてあって、交互に動かす。
駒は、今ある頂点と辺で繋がっていて、今ある頂点よりレベルの高い頂点に動かすことができる。
自分の手番に駒を動かせなくなったほうが負けである。両者最適に行動した場合にどちらが勝つか？

と考えると、このゲームの勝ち負けを後退解析で求める手順と元の問題で「どの頂点を選ぶか」を求める手順が一致します。そして負け状態に相当する頂点を選ぶことになります。

答えが一致するということは、このゲームを後退解析ではない別の手法で解いて負け状態を求めても、それがちゃんと元の問題の答えになっている、ということです。よってゲームの手法を用いてより高速な解法を考えることにします。

Grundy数の導入

ここでグラフの構造を思い出すと、駒の移動を3次元のグラフ $W$ で考える代わりに、各次元のグラフ $X, Y, Z$ にそれぞれ1個ずつ駒が置かれていると考えることができます。1回の移動は、

グラフ $X, Y, Z$ のうち1つを選ぶ。そこに置かれている駒を、今ある頂点と辺で繋がっていて、今ある頂点よりレベルの高い頂点に動かす。

と見なすことができます。

f:id:betrue12:20200702191550p:plain

このような「独立に動作する複数の部分ゲームがあって、1ターンにはそのうち1つを選んで1手動かす」というゲームにおいて力を発揮するのがGrundy数です。 $X, Y, Z$ それぞれのグラフにおいて各頂点のGrundy数を求めれば、状態 $(x, y, z)$ の勝ち負けは3つのGrundy数のXORが $0$ かどうかで判定することができます。負け状態、つまりこのXORが $0$ であるような頂点が、元の問題で選ばれる頂点です。

答えを求める！

それでは計算をしていきましょう。まずは各次元のグラフ $X, Y, Z$ について頂点の重みを $10^{18x}, 10^{18y}, 10^{18z}$ と定義します。そして「Grundy数が $g$ であるような頂点の重み和」をそれぞれ $S_{X}(g), S_{Y}(g), S_{Z}(g)$ としてこれを全て計算します。

3次元のグラフ $W$ の頂点 $(x, y, z)$ について、 $x, y$ 座標のGrundy数の組 $(g_{X}, g_{Y})$ を全探索します。そうすると $g_{Z} = g_{X} \oplus g_{Y}$ であるような頂点を選べば良いということになります（ $\oplus$ はXOR演算を表します）。このような頂点の重み和は、因数分解によって $S_{X}(g_{X})\times S_{Y}(g_{Y})\times S_{Z}(g_{Z})$ と計算することができます。

これを全て合計していくことで答えが求められます。

計算量は？

先ほどの解法は $(g_{X}, g_{Y})$ を全探索しています。これは間に合うのでしょうか？それを評価するために、Grundy数が最大でどれだけの値になるかを確認します。

Grundy数は「そこから遷移可能な頂点のGrundy数として登場しない最小の非負整数」です。つまりGrundy数が $G$ である頂点は、Grundy数が $0, 1, ..., G-1$ である頂点全てに遷移可能でなければいけません。そしてGrundy数 $G-1$ の頂点も $0, 1, ..., G-2$ の頂点に遷移可能で…と考えると、Grundy数 $G$ を実現するためには少なくとも $\frac{G(G+1)}{2}$ 本の辺が必要であることが分かります。

そのためグラフ $X, Y$ の辺の本数 $M_{1}, M_{2}$ を用いて、 $g_{X}, g_{Y}$ の最大値をそれぞれ $O(\sqrt{M_{1}}), O(\sqrt{M_{2}})$ と評価することができます。これなら $(g_{X}, g_{Y})$ を全探索しても大丈夫です。