想定解じゃなさげだけど、通ったからいいか。
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の時回ループするので、各ループの中ではあまり重いことはできない。
このループ中では、行列に左上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処理間で最小値を取ればよい。
ただし、上記の手順はかかり、最大ケースでギリギリ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を回避するの、何度も出てきたしね。