日立製作所 社会システム事業部 プログラミングコンテスト2020 : E - Odd Sum Rectangles

勘で解いてしまった…。
https://atcoder.jp/contests/hitachi2020/tasks/hitachi2020_e

問題

整数N,Mが与えられる。
(2^N-1)*(2^M-1)のグリッド上に01を配置し、そのうちの矩形範囲における1の数が奇数になるケースを最大化せよ。

解法

以下ちゃんと証明せずにやってしまった。
縦横長さが奇数なので、何となく真ん中には1を置いておくとよさそうである。
そこで、真ん中に1を置き、その他真ん中の列・行は空にしておく。
そうすると残された領域はやはり奇数×奇数の領域が4つになるので、再帰的に同じ処理を行っていく。

int N,M,H,W;
int A[1024][1024];

int B[1024][1024];
void check() {
	int x,y;
	FOR(y,H) FOR(x,W) {
		B[y+1][x+1]=B[y][x+1]+B[y+1][x]-B[y][x]+A[y][x];
	}
	int ret=0,sum=0;
	int x1,x2,y1,y2;
	FOR(x2,W) FOR(x1,x2+1) FOR(y2,H) FOR(y1,y2+1) {
		int num=B[y2+1][x2+1]-B[y1][x2+1]-B[y2+1][x1]+B[y1][x1];
		if(num%2==1) ret++;
		sum++;
	}
	cout<<ret<<"/"<<sum<<endl;
}


void dfs(int y1,int y2,int x1,int x2) {
	if(y1>y2 || x1>x2) return;
	int my=(y1+y2)/2;
	int mx=(x1+x2)/2;
	A[my][mx]=1;
	dfs(y1,my-1,x1,mx-1);
	dfs(y1,my-1,mx+1,x2);
	dfs(my+1,y2,x1,mx-1);
	dfs(my+1,y2,mx+1,x2);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	H=(1<<N)-1;
	W=(1<<M)-1;
	
	dfs(0,H-1,0,W-1);
	//check();
	
	FOR(y,H) {
		FOR(x,W) cout<<A[y][x];
		cout<<endl;
	}
	
}

まとめ

本番はカウントする関数だけ上記の通り作って、「まぁ再帰的にどうにかやればいいだろ」と思って割と良い値が出たから投げたら通ってしまった…。