kmjp's blog

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

yukicoder : No.923 オセロきりきざむたん

実装はともかく考察が大変。
https://yukicoder.me/problems/no/923

問題

01で構成されたグリッドが与えられる。
大きさ2以上のグリッドを選び、枠に平行な直線で2つに分割するということを行う。
その際、分割したいずれか片方を選択し、内部のセルの01を反転させる。

上記処理を繰り返し、グリッドが完全に1セルずつに分割されたとき、全部が1になるようにできるか。

解法

高さ1のグリッドを考える。
もしすべて0だと、分割時に毎回1個は0のマスが残るので、全部1にはできない。全部1の時も同様である。
逆に01が1個ずつ以上含まれていれば、常に条件を満たせる。
10または01と隣接している箇所があったとする。

それ以外の場所を、端から1個ずつ切り落としていくことを考える。
端の1を切り落とすなら、残った10を含む側を反転させればよいし、0を切り落とすならそちらを1に反転させればよい。
いずれにせよ01か10の構成が残るので、残り2つになったら0を反転させればよい。

よって、

  • 全列に01両方が現れる
  • 全行に01両方が現れる

のいずれかを満たせばよい。

int H,W;
string A[101010];
int R[101010],C[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>A[y];
		FOR(x,W) {
			R[y] |= 1<<(A[y][x]-'0');
			C[x] |= 1<<(A[y][x]-'0');
		}
	}
	if(H==1) {
		if(R[0]!=3) return _P("NO\n");
		cout<<"YES"<<endl;
	}
	else if(W==1) {
		if(C[0]!=3) return _P("NO\n");
		cout<<"YES"<<endl;
	}
	else {
		int ng=0;
		FOR(y,H) if(R[y]!=3) ng=1;
		if(ng==0) return _P("YES\n");
		ng=0;
		FOR(x,W) if(C[x]!=3) ng=1;
		if(ng==0) return _P("YES\n");
		return _P("NO\n");
	}
	
}

まとめ

よくこういう問題と解法思いつくなぁ。