kmjp's blog

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

AtCoder ARC #025 : A - ゴールドラッシュ、B - チョコレート

ARC025に参加。Dを部分点早解きしてそこそこの順位を得た。
http://arc025.contest.atcoder.jp/tasks/arc025_1
http://arc025.contest.atcoder.jp/tasks/arc025_2

A - ゴールドラッシュ

2つの鉱山において、7日間のそれぞれに得られる採掘量D[i]、J[i]が与えられる。
各日に片方の鉱山しか採掘できない場合、総採掘量を最大化せよ。

max(D[i],J[i])を7日分足すだけ。

int D[8],J[8];

void solve() {
	int f,i,j,k,l,x,y;
	FOR(i,7) cin>>D[i];
	FOR(i,7) cin>>J[i];
	int r=0;
	FOR(i,7) r+=max(D[i],J[i]);
	cout << r << endl;
}

B - チョコレート

HxWの2次元グリッド状のチョコがあり、各セルのチョコの濃度C[y][x]が与えられる。
各セルは市松模様状に隣接セル同士は白黒のチョコとなっている。
このグリッドから長方形を抜き出したとき、白と黒のチョコの濃度の和が等しくなるようなもののうち、面積最大のものを答えよ。

まず、白黒チョコのうち片方の濃度を符号反転させておく。
すると、「白黒のチョコ濃度の和が等しい」=「濃度の総和が0である」となり扱いやすくなる。
後は2次元の累積和を取っておくことで長方形内の総和をO(1)で算出できるので、長方形を総当たりして濃度総和が0のものを選べばよい。

計算量は累積和の計算も、長方形の総当たりもO(H^2*W^2)。

int H,W,C[105][105];
ll sum[105][105];

void solve() {
	int f,i,j,k,l,x,y,y2,x2;
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) cin>>C[y][x];
	FOR(y,H) FOR(x,W) if((x+y)%2) C[y][x]=-C[y][x];
	FOR(y,H) FOR(x,W) {
		FOR(y2,y+1) FOR(x2,x+1) sum[y+1][x+1]+=C[y2][x2];
	}
	int ma=0;
	int h,w;
	FOR(y,H) FOR(x,W) {
		for(h=1;y+h<=H;h++) for(w=1;x+w<=W;w++) if(h*w>ma) {
			if(sum[y+h][x+w]-sum[y+h][x]-sum[y][x+w]+sum[y][x]==0) ma=h*w;
		}
	}
	cout << ma << endl;
}

まとめ

A,Bまではすんなり。