E - Unfair Game Editorial
by 
sounansya
まず、 \(1\) つの袋のみを使って \(2\) 人でゲームをした時にどちらが勝つかを考えます。すると、「はじめ高橋君が袋を持っていた時にどちらが勝つか」「はじめ青木君が袋を持っていた時にどちらが勝つか」の \(2\) つの情報から、各袋は以下の \(4\) つに分類されます。
- 高橋君必勝：はじめ袋を持っているのがどちらであっても高橋君が勝つ。
- 青木君必勝：はじめ袋を持っているのがどちらであっても青木君が勝つ。
- 先手必勝：はじめ高橋君が持っている際は高橋君が勝ち、はじめ青木君が持っている際は青木君が勝つ。
- 後手必勝：はじめ高橋君が持っている際は青木君が勝ち、はじめ青木君が持っている際は高橋君が勝つ。
ここで、次が高橋君の番である状況下で高橋君が持っている袋のうち高橋君必勝か先手必勝である袋の数を \(A\) 、青木君が持っている袋のうち青木君必勝か先手必勝である袋の数を \(B\) とすると、以下の重要な事実が成立します。
- 問題の状況下で高橋君が勝てる必要十分条件は \(A>B\) である。
以下では $A>B$ なら高橋君が勝つことを証明します。 $A\le B$ なら青木君が勝つことも以下と同様に証明することができます。 現在の $A,B$ の値をそれぞれ $a,b$ とします。 高橋君は $A$ に数えられる袋に対し、青木君に渡しても新たに $B$ に数えられない操作をすれば良いです（このような操作は常に可能です）。 もし青木君が $B$ に数えられる袋に対する操作をした場合、新しい $A,B$ はそれぞれ $a,b-1$ か $a-1,b-1$ になります。逆に青木君が $B$ に数えられる袋に対する操作をした場合、新しい $A,B$ はそれぞれ $a,b$ か $a+1,b$ になります。どの場合でも $A-B\geq a-b>0$ が成立します。高橋君は少なくとも $A$ の値だけ操作ができるので、先に操作ができなくなるのは青木君の方です。証明
また、金貨が \(A_i\) 枚、銀貨が \(B_i\) 枚入った袋が高橋君必勝・青木君必勝・先手必勝・後手必勝のどれであるかは以下のように判定することができます。
- \(X,Y\) が共に偶数の場合
- \(A_i+B_i\) が偶数なら後手必勝、奇数なら先手必勝。
- \(X,Y\) が共に奇数の場合
- \(B_i\) が偶数なら後手必勝、奇数なら先手必勝。
- \(X\) が偶数で \(Y\) が奇数の場合
- \(A_i=0\) の場合、\(B_i\) が偶数なら後手必勝、奇数なら先手必勝。
- \(A_i=1\) の場合、\(B_i\) が偶数なら高橋君必勝、奇数なら先手必勝。
- \(A_i\geq 2\) の場合、高橋君必勝。
- \(X\) が奇数で \(Y\) が偶数の場合
- \(A_i=0\) の場合、\(B_i\) が偶数なら後手必勝、奇数なら先手必勝。
- \(A_i=1\) の場合、\(B_i\) が偶数なら青木君必勝、奇数なら先手必勝。
- \(A_i\geq 2\) の場合、青木君必勝。
これらは \((A_i,B_i)\) の辞書順に数学的帰納法で証明することができます。
\(N\) 個の袋のうち、高橋君必勝である袋が \(c_0\) 個、青木君必勝である袋が \(c_1\) 個、先手必勝である袋が \(c_2\) 個、後手必勝である袋が \(c_3\) 個とすると、条件 \(A-B>0\) が成立するような袋の分配方法は形式的冪級数を用いて以下のように表されます。
\[\sum_{k>0}[x^k](x^1+x^0)^{c_0}(x^0+x^{-1})^{c_1}(x^1+x^{-1})^{c_2}(x^0+x^0)^{c_3}\]
この式を式変形すると、
\[ \begin{aligned} &\phantom{=} \sum_{k>0}[x^k](x^1+x^0)^{c_0}(x^0+x^{-1})^{c_1}(x^1+x^{-1})^{c_2}(x^0+x^0)^{c_3}\\ &=\sum_{k>0}[x^k]2^{c_3}x^{-c_1-c_2}(1+x)^{c_0+c_1}(1+x^2)^{c_2}\\ &=2^{c_3}\sum_{k>c_1+c_2}[x^k](1+x)^{c_0+c_1}(1+x^2)^{c_2}\\ \end{aligned} \]
となります。この式を元に二項定理・累積和を用いることで答えを求めることができます。
以上でこの問題が解けました。計算量は \(O(N)\) です。
posted:
last update: