naoya_t@topcoder

SRM472 Div1 Easy(250): PotatoGame

過去問, 初心者記事 | 17:20 |

Nimとかこういう石取り・芋喰い系ゲームが苦手…

• 普通だったらDPで解くような問題なのだが
  • 今回は1e9までなので、DPしてたら間に合わない(ローカルマシンで60秒超)。パターンを見つけて数式を書くだけ
• 大抵、両者が最適手を打つ、というのをすごく難しく考えてしまって破滅する
• 落ち着いて順序を追って考えたらある重要かつ初歩的な事実に気がついた

芋数がNのとき、それは先手必勝か後手必勝かのどちらかしかない

次回、眠くても目を瞑ってても解けるようにメモしておく。恥ずかしい記事なのでDiv1の人は見ないようにｗ

N=0: もう取るものがない。先手必敗・後手必勝。// dp[0] = G;

N=1: 先手は1をとるしかない。残りが0(後手必勝)なので先手必勝。// dp[1] = S;

N=2: 先手は1をとるしかない。残りが1(先手必勝)なので後手必勝。// dp[2] = G;

N=3: 先手は1をとるしかない。残りが2(後手必勝)なので先手必勝。// dp[3] = S;

N=4: 先手は1をとるか4をとるか選べる。

• 4をとれば残りが0(後手必勝)なので勝てる
• 1をとれば残りが3(先手必勝)なので負ける
• 先手必勝手（＝取った先が後手必勝）がある場合はそれを取る（のが最適手というものだ）。どれを取っても先手必勝なら仕方がない（後手必勝）
• というわけでこの場合、4を取って先手必勝。// dp[4] = S;

N=5: 先手は1をとるか4をとるか選べる。

• 4をとれば残りが1(先手必勝)なので負ける
• 1をとれば残りが4(先手必勝)なので負ける
• というわけで、勝てる手がないので先手必敗。// dp[5] = G;

N=6: 先手は１をとるか４をとるか選べる。

• 4をとれば残りが2(後手必勝)なので勝てる。
• 1をとれば残りが5(後手必勝)なので勝てる。
• というわけで、どちらを取っても勝てる。先手必勝。// dp[6] = S;

こんな感じのことをDPで調べていけばよい。

  if(i>=1 && dp[i-1]==G) dp[i]=S;
  else if(i>=4 && dp[i-4]==G) dp[i]=S;
  else if(i>=16 && dp[i-16]==G) dp[i]=S;
  ...
  else dp[i]=G; // 1手先は後手必勝でないなら先手必勝。

適当なNまで見てみると

{ G, S, G, S, S, G, S, G, S, S, G, S, G, S, S, G, S, G, S, S, G, S, G, S, S, ... }

といった感じで、周期５でパターンが繰り返されている。N mod 5が0か2ならG, 1,3,4ならTが来る。（この問題ではGが後手の"Hanako"、Sが先手の"Taro"に対応）

答えが

    return (N%5==0||N%5==2)?"Hanako":"Taro";

でいいのかどうか、プログラムを書いてDP結果と照合してみたら、1<=N<=1e9の範囲で完全に一致した。（が、このチェックには1分46秒かかった。DPで解いていたら到底間に合わない）