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まではすんなり。