TopCoder SRM 744 Div1 Medium UniformingMatrix

これは本番すぐに方針が見えたので、むしろ周りがなぜそんなに落ちたかが謎。
https://community.topcoder.com/stat?c=problem_statement&pm=15210

問題

01で構成される行列がある。
ある要素を指定し、以下の処理を同時に行う、ということを繰り返す。

• その要素と同じ行の要素について、その要素以外を0/1反転する
• その要素と同じ列の要素について、その要素以外を0/1反転する

最終的に全要素1にできるか判定せよ。

解法

問題文を言い換えよう。
指定した要素自体は処理によって0/1判定しないが、言い方を変えると行と列両方の反転の影響を受け結果的に反転しない、と考えることができる。

そうすると、問題文の処理内容は、「行と列を指定してそれぞれ反転する」と言い換えられる。
よって、以下を判定すればよい。

• 行と列を指定して0/1反転する、という作業を繰り返したとき、
  • 全体を1にできる
  • 行と列の反転回数の偶奇が一致する

以下のコードではこのように判定している。

• 1行目の反転の有無を総当たりする。
  • 1行目の反転の有無が確定すれば、1行目の要素の内容から各列の反転の有無が確定する。
  • その後、1列目の内容から2行目以降の反転の有無を確定させる。
  • 最後に上記条件をチェックする。

int A[101][101];

class UniformingMatrix {
	public:
	string isPossible(vector <string> M) {
		int H=M.size();
		int W=M[0].size();
		int y,x,i;
		
		FOR(i,2) {
			FOR(y,H) FOR(x,W) A[y][x]=M[y][x]=='0';
		
			int R=i,C=0;
			FOR(x,W) A[0][x]^=i;
			
			FOR(x,W) if(A[0][x]) {
				C^=1;
				FOR(y,H) A[y][x]^=1;
			}
			
			for(y=1;y<H;y++) if(A[y][0]) {
				R^=1;
				FOR(x,W) A[y][x]^=1;
			}
			
			if(R!=C) continue;
			int sum=0;
			FOR(y,H) FOR(x,W) sum+=A[y][x];
			if(sum) continue;
			
			return "possible";
		}
		
		return "impossible";
	}
}

まとめ

450ptでもいいのにな。