torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder SRM 606, Division 2, Level 3 : EllysCandyGame

問題概要

 次のような二人ゲームをする。

  • N 個の箱があり、それぞれの中にはいくつかの飴が入っている
  • プレイヤーは交互に次の行動をする
    1. 空でない箱を一つ選び、その中にある飴を全て取る
    2. 選んだ箱の隣の箱の飴の数を倍にする

全ての箱が空になったときゲームが終了し、より多くの飴を持っていたプレイヤーが勝利する。同数である場合は引き分けとなる。
 箱の初期状態が与えられる。両者が最善を尽くしたときの勝敗を求めよ。なお、箱の数 ≦ 10 である。

解法

 箱の数に関する制約から、「既に取られた箱」の状態数は 2^{10} 通りになります。そのそれぞれについて、そこに至る飴の取り方は、取られた箱の数を b とすると 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;
	}
};