Div2 500, Div1 250 PotatoGame

問題

スタートの数Nに対して，2人のプレイヤーが交互に数を減らしていく．減らす数は4^k(1, 4, 16, 64…)で，計算結果が負の数になるのは駄目で，丁度0にしたプレイヤーが勝ちである．必勝は先攻(Taro)，後攻(Hanako)のどちらか？

考え方

競技中ならDPである程度の数までの必勝側を見て条件を見つければいい．証明の点で不安残るんだろうけど．
DP プログラムの例はこちら．先攻負けで初期化しておいて，「先攻負け状態へ行けるものは先攻勝ち」になるを繰り返せば OK．

#include <iostream>
#include <vector>
using namespace std;

int main(void)
{
  const int n = 100;
  vector<bool> win(n, false);
  for( int i = 0 ; i < n ; ++i ) {
    if( win[i] ) continue;
    for( int j = 1 ; i + j < n ; j *= 4 ) win[i+j] = true;
  }
  for( int i = 0 ; i < n ; ++i ) cout << (i%10);
  cout << "\n";
  for( int i = 0 ; i < n ; ++i ) cout << "XO"[(int)win[i]];
  cout << "\n";

  return 0;
}

で，出力がこちら．

0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789
XOXOOXOXOOXOXOOXOXOOXOXOOXOXOOXOXOOXOXOOXOXOOXOXOOXOXOOXOXOOXOXOOXOXOOXOXOOXOXOOXOXOOXOXOOXOXOOXOXOO

1 行目が N の一の位を示している．状況的に N mod 5＝1,3,4 だと先攻勝ちになりそうだ，ということでプログラムは組む．

が，ここは時間制限なんてないので枠を広げて一般的な場合として 4 → M，つまり減らせる数が M^k だとして考える．
mod (M+1) で考えると，M^k≡-1^k＝±1 なので N←N±1 の２択の遷移を選んでいるだけである．ただし N≦M においては N←N-1 しか選択肢が無い．
別の見方をすると，N≡M≡-1 の場合は +1 させる選択肢が常に存在し，他の場合は -1 させることしかできない場合がある．
なので N≡M 以外では実質的に +1 させる選択肢が無いと考えると，自分のターンが回ってきた時 N≡n が偶数だと N≡0 への変更があり得ないので必敗である．M が偶数の場合，-n と M+1-n とで偶奇が異なるが，必勝側は必勝選択肢を取るので N≡-1 以外では +1 の選択肢は本質的に無いと考えることになる．
つまり N≡2k+1 or M であれば必勝，他は必敗である．これを元の問題に当てはめると，N≡1,3,4の場合に太郎は必勝，他は花子が必勝になる．

コード

#include <string>
using namespace std;

class PotatoGame
{
public:
  string theWinner(int n)
  {
    n %= 5;
    return (n==0||n==2)?"Hanako":"Taro";
  }
};