salt - SALT TREE XV Editorial
by 
Mitsubachi
初めに、以下の性質を示します。
- $N(>0)$ 頂点の木のgrundy数は $N$ が奇数の時 $1$ であり、そうでなければ $2$ である。
証明
$g(N)$ を $N$ 頂点の木のgrundy数とします。便宜上 $g(0)=0$ とします。 $N$ に関する帰納法で示します。
$N=1$ の時、頂点を取るしか手はないので操作終了時のgrundy数は $0$ です。よって $g(1)= \mathrm{mex}(0) = 1$ です。
$1 \leq N \leq X$ で性質が成り立っているとして、 $N=X+1$ でも成り立つことを示します。
$X+1$ が偶数とします。操作後の森のgrundy数を $0$ とするには辺を $1$ つ選んで操作すれば森は頂点数の偶奇が同じ木が $2$ つとなるのでこれでよいです。 $1$ とするには葉を $1$ つ選んで操作すればよいです。
$2$ にできないことを示します。操作後の森でgrundy数が $2$ となるようなものがあると仮定して背理法で示します。帰納法の仮定より森は偶数頂点の木が奇数個、奇数頂点の木が偶数個となり、森の頂点数は偶数となります。操作で高々頂点数は $1$ 減るので操作では辺を消したことになり森の木の数は $2$ となりますが、これは森の木の数が奇数であることに矛盾します。
よって $g(X+1)=2$ となり、この場合は示されました。
$X+1$ が奇数とします。操作後の森のgrundy数を $0$ とすることを考えます。帰納法の仮定よりgrundy数が $0$ の時、偶数頂点の木、奇数頂点の木は共に偶数個あるので森は偶数個の木からなります。よって、次数が偶数となる頂点について操作を行う必要があります。実は次数が偶数である頂点が存在することとこれで十分であることが示せます。
証明
まず、そのような頂点の存在を示します。全ての頂点の次数が奇数と仮定すると $X+1$ が奇数なので木の次数の総和は奇数となりますが、一般グラフにおいて次数の総和は偶数なので矛盾します。よって示されました。
次数が偶数である頂点に操作した際、森は偶数個の木からなり、 $X$ 個の頂点、すなわち偶数個の頂点を含んでいます。奇数頂点の木が奇数個あるとすると森の頂点数が奇数となり矛盾します。よって奇数頂点の木は偶数個あり、森は偶数個の木からなるので偶数頂点の木も偶数個あります。よって示されました。
従って、森のgrundy数を $0$ にできます。
$1$ にできないことを示します。辺に操作する場合、頂点数の偶奇が異なる木が $1$ つずつできるので森のgrundy数は $3$ となります。頂点に操作する場合、森の頂点数は偶数となるので奇数頂点の木は偶数個となります。よってgrundy数は $0$ もしくは $2$ となります。これより示されました。
よって $g(X+1)=1$ となり、この場合も示されました。
上より、 $N=X+1$ でも仮定が成り立つので数学的帰納法より示されました。
具体的に勝利する方法を考えます。常に先手が操作した後は森のgrundy数を $0$ とできることを示します。まず森はいくつかの木からなり木のgrundy数は $1$ か $2$ なので森のgrundy数は $0,1,2,3$ のいずれかです。
$1$ 手目は上よりよいです。grundy数の性質より後手の操作後森のgrundy数は $0$ でないので $1,2,3$ のいずれかとなります。
$1$ の時、偶数頂点の木が偶数個、奇数頂点の木が奇数個あります。奇数頂点の木にある次数が偶数の頂点を選択すればgrundy数を $0$ にできます。
$2$ の時、偶数頂点の木が奇数個、奇数頂点の木が偶数個あります。偶数頂点の木の辺を選択すればよいです。
$3$ の時、偶数頂点の木が奇数個、奇数頂点の木が奇数個あります。偶数頂点の木の葉を選択すればよいです。
よって示されました。ゲームは \(O(n)\) ターンであり、操作に適切な辺もしくは頂点を見つけるのに \(O(n)\) なのでこの問題は \(O(n^2)\) で解けました。
posted:
last update: