kmjp's blog

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

yukicoder : No.819 Enjapma game

実装だけ見るとラクなんだよな。
https://yukicoder.me/problems/no/819

問題

グリッド上にいくつかの駒がある。
ここで2人交互にターンが来るゲームを行う。

各人のターンが来たとき、駒が0個だと負けである。
そうでない場合、駒を1つ選択して、

  • 取り除く
  • 盤面の外に出ず、かつ駒が同じマスに2つ以上重複しない範囲で、1個マス左か下に動かす

のいずれかを行うものとする。
最適手を取るとき、先手後手どちらが必勝か判定せよ。

解法

Editorialを見てしまったので、解だけ示す。
左下角のマスを白とし、グリッドを白黒マスで塗り分けよう。
白マス上の駒をスコア1、黒マス上の駒をスコア2とすると、スコアの総和が3の倍数で自分の番が来ると負けである。

これは以下2つの事実から示せる。

  • スコアの総和が3の倍数である場合、どの手順をとっても操作後のスコアは3の倍数ではなくなる。
  • スコアの総和が3の倍数でない場合、3の倍数にできる手順が必ずある。
int H,W;
string S[202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	int nim=0;
	FOR(y,H) cin>>S[H-1-y];
	FOR(y,H) {
		FOR(x,W) if(S[y][x]=='o') {
			if((x+y)%2) nim+=2;
			else nim+=1;
		}
	}
	if(nim%3) cout<<"NO"<<endl;
	else cout<<"YES"<<endl;
}

まとめ

勝ち負けを求める問題で、mod2が出てくる問題は良くあるけど、mod3が出てくるのは珍しいね。