Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2012-03-03SRM534 Div1(Practice)

SRM534 Div1 250 EllysCheckers

| 17:24 | SRM534 Div1 250 EllysCheckers - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM534 Div1 250 EllysCheckers - SRM diary(Sigmar) SRM534 Div1 250 EllysCheckers - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

普通にビットでメモ化再帰した

DP/メモ化で解ける問題はそのほうが確実性が高いように思うのでもっと効率のいい方法を考えることはしていない

しかし結構実装が大変・・・


ソースコード

int memo[1<<20];

class EllysCheckers {
public:
	int n;

	int rec(int mask) {
		if(memo[mask]>=0) return memo[mask];

		int res=0;
		for(int i=0; i<n-1; i++) {
			if(!(mask&(1<<i))) continue;
			if(!(mask&(1<<(i+1)))) {
				int nmask=(mask^(1<<i));
				if(i+1<n-1) nmask^=(1<<(i+1));
				if(rec(nmask)==0) res=1;
			}
			if(i+3<n && (mask&(1<<(i+1))) && (mask&(1<<(i+2))) && !(mask&(1<<(i+3)))) {
				int nmask=(mask^(1<<i));
				if(i+3<n-1) nmask^=(1<<(i+3));
				if(rec(nmask)==0) res=1;
			}
		}

		memo[mask]=res;
		return res;
	}

	string getWinner(string board) {
		string res;
		n=board.size();

		memset(memo, -1, sizeof(memo));
		int beg=0;
		for(int i=0; i<n-1; i++) {
			if(board[i]=='o') beg|=(1<<i);
		}
		if(rec(beg)) res="YES";
		else res="NO";
		
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120303