問題概要
次のような二人ゲームをする。
- N 個の箱があり、それぞれの中にはいくつかの飴が入っている
- プレイヤーは交互に次の行動をする
- 空でない箱を一つ選び、その中にある飴を全て取る
- 選んだ箱の隣の箱の飴の数を倍にする
全ての箱が空になったときゲームが終了し、より多くの飴を持っていたプレイヤーが勝利する。同数である場合は引き分けとなる。
箱の初期状態が与えられる。両者が最善を尽くしたときの勝敗を求めよ。なお、箱の数 ≦ 10 である。
解法
箱の数に関する制約から、「既に取られた箱」の状態数は 通りになります。そのそれぞれについて、そこに至る飴の取り方は、取られた箱の数を b とすると 通りあります。箱の各状態についてこの値を計算して和をとると 9,864,101 です。すなわち、ゲーム全体の状態数は 9,864,101 であると分かります。
状態数がそれなりに少ないので、展開を全て読み切ることができます。従って、適当に Mini-Max 法などを実装することで解くことができます。
コード
typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<string> VS; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define FOR( v, c ) for ( auto &v : c ) #define ALL( c ) (c).begin(), (c).end() const int ds[] = { -1, 1 }; class EllysCandyGame { public: int N; string getWinner( vector <int> sweets ) { N = sweets.size(); return VS{ "Kris", "Draw", "Elly" }[ rec( sweets, 0, 0, true ) + 1 ]; } int rec( VI &boxes, const int a, const int b, bool elly ) { if ( count( ALL( boxes ), 0 ) == N ) { if ( a == b ) { return 0; } return a < b ? -1 : 1; } int res = elly ? -1 : 1; REP( i, 0, N ) { if ( boxes[i] ) { const int na = elly ? a + boxes[i] : a; const int nb = elly ? b : b + boxes[i]; VI tmp = boxes; tmp[i] = 0; if ( 0 < i ) { tmp[ i - 1 ] *= 2; } if ( i + 1 < N ) { tmp[ i + 1 ] *= 2; } res = elly ? max( res, rec( tmp, na, nb, !elly ) ) : min( res, rec( tmp, na, nb, !elly ) ); } } return res; } };