D - Alice&Brown

D - Alice&Brown
解説PDFで実験について触れられてなくて悲しくなったので

この問題の想定解は実験です（断言）
解説は帰納法って書いてるけど帰納法使うためには予想が必要だからね
どう言う問題だと実験をするべきかなんだけど
・ゲーム問題であること（返り値が0/1なので結果から法則が見えやすい）
・入力が定数個であること（入力個数が変数の場合調べる対象が多すぎる）
・実験コードが書きやすい（書きたいので）
・何も思いつかない（まずは1分くらい考察して見るべき）
この辺を満たしていたら実験するべきだと思う
手で実験してもいいんだけど、競プロやってるならせっかくだからプログラムを書きましょうね
あと手でかける範囲だと規則が見えにくいことが多いと言うのもある

とりあえず実験コードをドーン

#include <bits/stdc++.h>
using namespace std;

int dp[1000][1000];
//f(i,j):二つの山の石がi個、j個の状態で自分に回って来た時に勝てるか
bool f(int i,int j){
  if(~dp[i][j])return dp[i][j];
  for(int k=1;k*2<=i;k++)if(!f(i-k*2,j+k))return dp[i][j]=1;
  for(int k=1;k*2<=j;k++)if(!f(i+k,j-k*2))return dp[i][j]=1;
  return dp[i][j]=0;
}

int main(){
  memset(dp,-1,sizeof(dp));
  for(int i=0;i<30;i++)
    for(int j=0;j<30;j++)
      cout<<i<<" "<<j<<" "<<f(i,j)<<endl;
}

書き方は自由だけど一応割とシンプルで流用の効くものかなと思ってる
軽く解説しておくと
・記憶用のdp配列を取っておいて最初に-1で全部初期化
・一手で負けに持っていける盤面が勝ち、無いなら負け

このコードを実行すると

こんな感じになる（もっと下まで続く）
これを適当に見て閃けばそれでOK
見づらいと感じたら例えば出力部分を

int main(){
  memset(dp,-1,sizeof(dp));
  for(int i=0;i<30;i++){
    for(int j=0;j<30;j++)cout<<f(i,j)<<" ";
    cout<<endl;
  }
}

に変えてあげれば

多少見やすくなったりする
問題ごとにどう言う出力が見やすいかは違うかな
変数3つあったりすると二次元表示は出来ないし

おまけ

Programming Problems and Competitions :: HackerRank
このコンテストの最後の問題が入力定数個のゲーム問題だけど実験から規則性見えないタイプなので一応
他の問題も緑~水色の知識があれば解けるので解こうね
このコンテストの解説記事