右手に栄光を　分析せよ

この手のプログラム間違えることが多々あるので疑り深く読んでほしいです！！！

作品内では扉のロックである以上攻略できるようになっているが、あれってちゃんとやっても右手（後手、プレイヤー）必勝なのか、左手（先手、扉）が忖度しているのか、どっちなんですか、という話。こういうゲームって先手ゲーの印象があるので。てかだいぶ先手有利ゲーに見えるなこれ、こっちのほうが勝利条件厳しいし。

ルールを再確認しよう。面倒なのでカードゲームにする。

ゲームは2人で行う。各プレイヤーは1以上5以下の整数がそれぞれ書かれたカード計5枚を手札として持っている。各プレイヤーは自分の番に以下の操作を1回のみ行う。パスは許されない。

操作：自分の手札を1枚選び、場に出す。

場のカードに書かれた数の和がちょうど23になった場合（それがどちらの手番であっても）その時点で後手の勝利、24以上になった場合先手の勝利である。

こういうゲームは数学的にいい感じの証明を与えることができそうな気がするが、数学的に考えるのは面倒（というか僕には無理っぽい気が）なので計算機で殴りたいと思う。各カードは場にあるか手札にあるかのどちらかなので、状態数はたかだか2¹⁰=1024（実際は両者の手札の枚数差の制約があってもっと小さい）。多分余裕。

実装は、メモ化再帰みたいな感じにすれば解けそう。

dp[a][b] = 先手の手札の状態がa、後手の手札の状態がbのとき、現在の手番の者が必勝か否か

としてやれば、dp[先手の手札5枚][後手の手札5枚]がtrueかfalseかでどちらが必勝かわかる。

遷移だが、テーブルの埋め方は（総和23以上の自明な場合を除いて）一手先の状態が全部trueならfalse、そうでなければtrue。

C++での実装は以下。間違ってたら言って、結論が間違ってる説まであるので。

注意：出力はoutput.csvというファイルに書き込まれるので消えると困るoutput.csvがある場所では実行しないようにしてください、または出力ファイル名のところを書き換えるなどしてください

#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

vector<vector<int>> dp;
vector<int> w;

int dfs(int a, int b, int sum){
  // a,b: 下5bitが各人の手札[5][4][3][2][1]が場に出てるフラグ, aが先手
  if(dp[a][b]!=-1) return dp[a][b];
  // t: 場に出てる枚数, 今が先手番かわかる
  int t = __builtin_popcount(a) + __builtin_popcount(b);
  if(t%2==0){
    // 先手の番
    if(sum==23) dp[a][b] = 0;
    else if(sum>23) dp[a][b] = 1;
    else{
      int res = 0;
      for(int i=0;i<5;i++){
        if(a&(1<<i)) continue;
        if(dfs(a|(1<<i),b,sum+w[i])==0) res=1;
      }
      dp[a][b] = res;
    }
  }
  else{
    // 後手の番
    if(sum==23) dp[a][b] = 1;
    else if(sum>23) dp[a][b] = 0;
    else{
      int res = 0;
      for(int i=0;i<5;i++){
        if(b&(1<<i)) continue;
        if(dfs(a,b|(1<<i),sum+w[i])==0) res=1;
      }
      dp[a][b] = res;
    }
  }
  return dp[a][b];
}

// 出したカード
string f(int a){
  string res = "";
  for(int i=0;i<5;i++){
    if(a&(1<<i)) res += to_string(w[i]);
  }
  if(a==0) res="none";
  return res;
}

// 出したカードの和
string s(int a){
  int sum = 0;
  for(int i=0;i<5;i++){
    if(a&(1<<i)) sum += w[i];
  }
  return to_string(sum);
}

int main(){
  // 出力ファイル
  ofstream ofs("output.csv");
  cout.rdbuf(ofs.rdbuf());

  // 初期化
  dp.assign(32,vector<int>(32,-1));
  w.resize(5);
  for(int i=0;i<5;i++) w[i] = i+1;

  // 探索
  dfs(0,0,0);

  // その手番のプレイヤーが必勝か？->後手必勝か？に変換
  for(int i=0;i<32;i++){
    for(int j=0;j<32;j++){
      if(dp[i][j]==-1) continue;
      dp[i][j] = (dp[i][j]+1+__builtin_popcount(i)+__builtin_popcount(j))%2;
    }
  }

  // 出力
  string xo = "xo";
  cout << ',';
  cout << "wakaru";
  for(int i=0;i<32;i++){
    cout << ',' << f(i);
  }
  cout << endl;
  cout << "door";
  cout << ',';
  for(int i=0;i<32;i++){
    cout << ',' << s(i);
  }
  cout << endl;
  for(int i=0;i<32;i++){
    cout << f(i) << ',' << s(i);
    for(int j=0;j<32;j++){
      cout << ',' << ((dp[i][j]==-1)?' ':xo[dp[i][j]]);
    }
    cout << endl;
  }

  return 0;
}