kmjp's blog

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

TopCoder SRM 600 Div1 Medium PalindromeMatrix

想定解じゃなさげだけど、通ったからいいか。
http://community.topcoder.com/stat?c=problem_statement&pm=12875

問題

N行M列(N,Mは偶数)の0,1からなる行列Aが与えられる。
この行列から、行方向及び列方向に数字を並べたとき、回文になっている行がrowCount以上、列がcolCount以上になるようにしたい。
条件を満たすには、行列中の要素を最小でいくつ書き換えればよいか答えよ。

解法

どっかで似たようなのあるな…と思ったらこれだった。
Codeforces #194 Div1.B Chips
実際この問題の知見があったおかげで回答できている。

想定解法の計算量を見るに、以下は想定解と異なると思うけど一応書いておく。
N,Mが14以下と小さいので、N行M列のうちどのrowCount行・colCount列を回文にするかをbitmapで持ち、総当たりする。
最大ではrowCount=colCount=7の時 ({}_{14} C_7)^2=11778624回ループするので、各ループの中ではあまり重いことはできない。

このループ中では、行列に左上1/4、すなわち上N/2行左M/2列に対し以下の値を合計する。
今y行x列を見ているとすると、A(y,x)の値は回文作成の上でA(y,W-1-x)・A(H-1-y,x)・A(y,W-1-x)と関連する。

  • y行目を回文にするなら、A(y,x)==A(y,W-1-x)でなければならない
  • (H-1-y)行目を回文にするなら、A(H-1-y,x)==A(H-1-y,W-1-x)でなければならない
  • x列を回文にするなら、A(y,x)==A(H-1-y,W-1-x)でなければならない
  • (W-1-x)列目を回文にするなら、A(y,W-1-x)==A(H-1-y,W-1-x)でなければならない

すなわち、bitmapの値でループする際、各y,xについてy行目・(H-1-y)行目・x列目・(W-1-x)列目を回文にするかどうかでA(y,x)・A(y,W-1-x)・A(H-1-y,x)・A(y,W-1-x)を一致させる必要があるかどうかが決まる。
一致させなければいけない場所が確定したら、それらを0にそろえるのと1にそろえるので少ない書き換えで済むものを選べばよい。

上記書き換え回数を各y,xにおける和を求め、bitmap処理間で最小値を取ればよい。

ただし、上記の手順は ({}_{14} C_7)^2\times\frac{N}{2}\frac{M}{2}かかり、最大ケースでギリギリTLEする。
自分はSubmit後にそれを確認したので、bitmap毎ループ以内のy,xの処理を一部前処理し、yだけ回すようにして(ソース中コメント部)計算量を落とした。

int mm3[8][4][1<<14];
class PalindromeMatrix {
	public:
	int H,W;
	int mat[16][16];
	char mm2[8][8][16];
	int minChange(vector <string> A, int RC, int CC) {
		int y,x,ii,jj,res,t,i,yo1,yo2,xo1,xo2;
		int ym,xm;
		H=A.size();
		W=A[0].size();
		FOR(y,H/2) FOR(x,W/2) {
			mat[y][x]=(A[y][x]-'0')+(A[y][W-1-x]-'0')+(A[H-1-y][x]-'0')+(A[H-1-y][W-1-x]-'0');
		}
		res=H*W;
		vector<int> YM,XM;
		FOR(y,H/2) FOR(x,W/2) {
			int y2=H-1-y,x2=W-1-x;
			FOR(yo1,2) FOR(yo2,2) FOR(xo1,2) FOR(xo2,2) {
				int tr=0;
				if(yo1+yo2+xo1+xo2>=3) tr+=min(mat[y][x],4-mat[y][x]);
				else if(!xo1 && !xo2) {
					if(yo1) tr+=(A[y][x]!=A[y][x2]);
					if(yo2) tr+=(A[y2][x]!=A[y2][x2]);
				}
				else if(!yo1 && !yo2) {
					if(xo1) tr+=(A[y][x]!=A[y2][x]);
					if(xo2) tr+=(A[y][x2]!=A[y2][x2]);
				}
				else if(yo1&&xo1&&!yo2&&!xo2) t=A[y][x]+A[y2][x]+A[y][x2]-3*'0', tr+=min(t,3-t);
				else if(yo1&&xo2&&!yo2&&!xo1) t=A[y][x]+A[y2][x2]+A[y][x2]-3*'0', tr+=min(t,3-t);
				else if(yo2&&xo1&&!yo1&&!xo2) t=A[y2][x]+A[y2][x2]+A[y][x]-3*'0', tr+=min(t,3-t);
				else if(yo2&&xo2&&!yo1&&!xo1) t=A[y2][x2]+A[y][x2]+A[y2][x]-3*'0', tr+=min(t,3-t);
				mm2[y][x][yo1*8+yo2*4+xo1*2+xo2]=tr;
			}
		}
		ZERO(mm3);
		FOR(y,H/2) {
			FOR(ii,4) {
				FOR(xm,1<<W) {
					FOR(x,W/2) {
						int x2=W-1-x;
						int xo1=(xm>>x)&1;
						int xo2=(xm>>x2)&1;
						mm3[y][ii][xm]+=mm2[y][x][ii*4+xo1*2+xo2];
					}
				}
			}
		}
	
		
		FOR(i,1<<H) if(__builtin_popcount(i)==RC) YM.push_back(i);
		FOR(i,1<<W) if(__builtin_popcount(i)==CC) XM.push_back(i);
		FOR(ii,YM.size()) FOR(jj,XM.size()) {
			ym=YM[ii];xm=XM[jj];
			int tr=0;
			FOR(y,H/2) {
				int y2=H-1-y;
				int yo1=(ym>>y)&1;
				int yo2=(ym>>y2)&1;
				tr+=mm3[y][yo1*2+yo2][xm];
				/*
				FOR(x,W/2) {
					int x2=W-1-x;
					int xo1=(xm>>x)&1;
					int xo2=(xm>>x2)&1;
					tr+=mm2[y][x][yo1*8+yo2*4+xo1*2+xo2];
					if(tr>=res) break;
				}
				*/
				if(tr>=res) break;
			}
			res=min(res,tr);
		}
		return res;
	}
};

まとめ

もともと実装が重い問題らしいし、コピペが多く汚い書き方になってしまったけど、それでも本番中にこれを通せたのはCodeforcesの練習の成果がでてよかった。
総和の前処理でTLEを回避するの、何度も出てきたしね。