くだらないミスで落としてもったいない。
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; } }
まとめ
せっかく全完のチャンスだったのに落としてもったいない…。