kmjp's blog

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

Codeforces #190 Div1 D. Ciel and Flipboard

この回は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]について以下が成り立つ。

  1. 各列j<xについて、B[i][j] ^ B[i][x] ^ B[i][j+x] = 0
  2. 各行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;
	
}

まとめ

局所的な最大化を合わせて全体を最大化できるのが面白いね。