読者です 読者をやめる 読者になる 読者になる

Codeforces #399 E: Game of Stones

Grundy数 分割数 ビットDP

ニムのルールを少し変えたゲームの勝敗を知りたい。石の山の状態の数とその状態の遷移の数が十分小く表せれば、Grundy数やるだけ。
山の状態を適切に表したい。愚直に考えれば
山の状態=(石の個数, 1~60のうち取り除いたことのある個数についてのフラグ)
たとえば
s[0] = 10としよう。
この山の状態は
(10, まだ石を取り除いていない)
であり、ここから石を4個取ると
(10-4, 石を4個取り除いたことがある)
この状態からもう一度石を4個取り除くことはできない。
更に石を2個取り除いてみると
(10-4-2, 石を4個、2個取り除いたことがある)
このとき石の山からは4個も2個も取り除くことはできない。
このあと石の山から1個、3個取り除けば状態は
(0, 石を4個、2個、1個、3個取り除いたことがある)
となり、このときGrundy数は0

s[i]<=60より、取り除いたことのある石の個数のフラグは、ビット数から2^60通り。だが、実際にあり得る状態の数は十分少ない。説明する。
取り除いたことのある石の数の集合をTとする。たとえば先の例では最終的に、T={1,2,3,4}となっていた。
山に含まれる石の個数をxとすると、あるj(1<=j<=n)によって

s[j] = x + ΣT
つまり
もとの石の山
= (残りの個数) + (取り除いた個数)
= (残りの個数) + (T[0]+T[1]+...+T[k])
が成り立っている。
これにより、状態はs[j]以下の整数の分割の1種と対応することがわかる。よって、整数m(0<=m<=60)の分割数をp(m)としたとき、状態数は
p(m)を使って抑えられる。
Σp(m)
= 1 + 1 + 2 + 3 + 5 + 7 + ... + 966467 (https://oeis.org/A000041)
= 6639349
< 6.7 * 10^6

この程度なのでおそらく間に合う。

 

思いつき方
ビットDPやGrundy数を知っている。愚直解について考える。sの要素60以下で小さい。愚直解は(状態がスカスカの)ビットDP。愚直解の計算量を調べてみる。状態数はもともとの石の数の分割数で抑えられる。間に合う。