この回はEよりDの方が正答者が少ない。
http://codeforces.com/contest/321/problem/D
問題
奇数Nに対し、N*N要素の行列Aが与えられる。
この行列に対し、x=(N+1)/2としたとき、x*xの要素群の符号を反転する処理を任意回数行える。
行列要素の総和を最大化せよ。
解法
Editorialを見て回答。
B[i][j]をA[i][j]を符号反転した回数の偶奇とすると、B[1][1]~B[N][N]について以下が成り立つ。
- 各列j<xについて、B[i][j] ^ B[i][x] ^ B[i][j+x] = 0
- 各行i<xについて、B[i][j] ^ B[x][j] ^ B[i+x][j] = 0
あとはB[x][1]~B[x][x]のx要素分を総当たりしつつ、符号反転後のAの総和を最大化する。
B[x][1]~B[x][x]が決まると、上記ルール1よりB[x][x+1]~B[x][N]が決まり、x行目の内容が確定する。
次に、各行iにおいてB[i][x]を0と1で総当たりする。B[i][x]が決まるとB[x][x]が確定済みなので、B[i+x][x]が決まる。
次に、j<xについてB[i][j]を定めるわけだが、B[i][x]、B[x][j]、B[x][j+x]、B[i+x][x]がいずれも確定済みなので、B[i][j]を0か1総当たりするとB[i][j]、B[i+x][j]、B[i][j+x]、B[i+x][j+x]が確定するので、符号反転後のA[i][j]、A[i+x][j]、A[i][j+x]、A[i+x][j+x]の総和が最大化する方にB[i][j]を定める。
最終的に、B[i][x]の0,1に対してAのi行目およびi+x行目の最大値が求まる。
int N,L; int A[100][100]; int M[100][100]; int sc(int y,int x) { return M[y][x]?-A[y][x]:A[y][x]; } void solve() { int i,j,k,l,r,x,y,mask; string s; cin>>N; L=(N+1)/2; FOR(y,N) FOR(x,N) cin>>A[y][x]; int ret=-1<<30; FOR(mask,1<<L) { int sum=0; FOR(x,N) { if(x<L) M[L-1][x]=(mask&(1<<x))==0; else M[L-1][x]=M[L-1][L-1]^M[L-1][x-L]; sum += sc(L-1,x); } FOR(y,L-1) { int ts=-1<<30; FOR(i,2) { int cs=0; M[y][L-1]=i; M[y+L][L-1]=M[y][L-1]^M[L-1][L-1]; cs += sc(y,L-1)+sc(y+L,L-1); FOR(x,L-1) { int cs2=-1<<30; FOR(j,2) { M[y][x]=j; M[y][x+L]=M[y][x]^M[y][L-1]; M[y+L][x]=M[y][x]^M[L-1][x]; M[y+L][x+L]=M[y+L][x]^M[y+L][L-1]; cs2=max(cs2,sc(y,x)+sc(y,x+L)+sc(y+L,x)+sc(y+L,x+L)); } cs+=cs2; } ts=max(ts,cs); } sum+=ts; } ret=max(ret,sum); } cout<<ret<<endl; }
まとめ
局所的な最大化を合わせて全体を最大化できるのが面白いね。