SRM 534 250pt : EllysCheckers

問題概要

長さN(<20)のボードがあって各マスは空かチェッカーが置いてある。チェッカーは

1. 右の空のマスにずらす。
2. 1つ右、2つ右にチェッカーがあって3つ右が空のとき右に3つずらす。

のいずれかをする。最右にチェッカーが来たら即消す。交互に動かして、動かせなくなった方の負け。勝つのはどちらか求める問題。

解法

なんか賢い解き方あるらしいけどビットDPで間に合う。最右に来たチェッカーを消すというのに気づかずに色々時間をとられた。

acceptされたコード

計算量O(N*2^N)。

#include <string>
using namespace std;

int N;
const int MAX_N = 20;
bool visited[1<<MAX_N];
bool memo[1<<MAX_N];

struct EllysCheckers {

	string getWinner(string board) {
		N = board.length();
		int bit = 0;
		for(int i=0; i<N-1; i++)if(board[i] == 'o'){
			bit |= (1<<i);
		}

		return rec(bit) ? "YES" : "NO";
	}

	bool rec(int bit){
		if(visited[bit]){
			return memo[bit];
		}
		visited[bit] = true;

		bool& ret = memo[bit] = false;

		//STEP
		for(int i=0; i<N-1; i++)if(((bit>>i)&1) && !((bit>>(i+1))&1)){
			int nbit = bit | (1<<(i+1));
			nbit &= ~(1<<i);
			nbit &= ~(1<<(N-1));
			ret |= !rec(nbit);
		}

		//JUMP
		for(int i=0; i<N-3; i++)if( ((bit>>i)&1) && ((bit>>(i+1))&1) && ((bit>>(i+2))&1) && !((bit>>(i+3))&1)){
			int nbit = bit | (1<<(i+3));
			nbit &= ~(1<<i);
			nbit &= ~(1<<(N-1));
			ret |= !rec(nbit);
		}

		return ret;
	}
};