kmjp's blog

競技プログラミング参加記です

TopCoder SRM 738 Div1 Medium LightbulbGame

くだらないミスで落としてもったいない。
http://community.topcoder.com/stat?c=problem_statement&pm=15112

問題

グリッド上に並んだ電球がある。
2人ですべての電球を消すゲームを行う。
全部消えた状態で自分の手番が来ると負けである。

自分の手番では以下の処理を行える。

  • 点いている電球を一つ選び、消す。
    • その際、その電球の右もしくは下にある電球を1つ選び、オンオフ逆にすることができる。1つも選ばなくてもよい。

先手必勝とする場合、先手が取れる手は何通りか。

解法

Nimに落とし込めばよい。

各マスについて、そのマス1マスだけ電球が付いている場合のGrundy数を求めよう。
右もしくは下の各マスを点灯させたときのGrundy数を元に求めていく。

int H,W;
vector<string> S;

int nim[51][51];

class LightbulbGame {
	public:
	int countWinningMoves(vector <string> board) {
		S=board;
		H=S.size();
		W=S[0].size();
		
		int i,x,y;
		for(y=1;y<=H;y++) {
			for(x=1;x<=W;x++) {
				set<int> S;
				nim[y][x]=0;
				S.insert(0);
				for(i=1;i<y;i++) S.insert(nim[i][x]);
				for(i=1;i<x;i++) S.insert(nim[y][i]);
				while(S.count(nim[y][x])) nim[y][x]++;
			}
		}
		
		int tot=0;
		for(y=1;y<=H;y++) {
			for(x=1;x<=W;x++) {
				if(S[H-y][W-x]=='1') tot^=nim[y][x];
			}
		}
		
		int ret=0;
		for(y=1;y<=H;y++) {
			for(x=1;x<=W;x++) if(S[H-y][W-x]=='1') {
				tot^=nim[y][x];
				if(tot==0) ret++;
				for(int x2=1;x2<x;x2++) if(nim[y][x2]==tot) ret++;
				for(int y2=1;y2<y;y2++) if(nim[y2][x]==tot) ret++;
				tot^=nim[y][x];
			}
		}
		
		return ret;
	}
}

まとめ

せっかく全完のチャンスだったのに落としてもったいない…。