実装はともかく考察が大変。
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"); } }
まとめ
よくこういう問題と解法思いつくなぁ。