問題B『チョコレート』 : AtCoder Regular Contest 025

解法しか見当たらなかったので。

問題文 : チョコレート

概要

の盤面上に整数C[x,y]が書かれており、市松模様の色(白、黒)が塗られている。
盤面上に含まれる長方形領域のうち、その中に書かれた白と黒の総和が一致するようなものの面積の最大値を求めよ。

制約

解説

累積和をとって長方形を全列挙すれば一応で、/4のおかげでギリギリセーフだが…。

まず、x+yが奇数のときC[x,y]*=-1としておく。そうすると、白と黒の総和が一致、の代わりに、総和が0で済む。
そして、累積和をとる。

for (var i = 0; i < H; i++) for (var j = 0; j < W; j++) sum[i + 1, j + 1] = C[i][j] + sum[i, j + 1] + sum[i + 1, j] - sum[i, j];

そうすると、で指定された長方形の中身の総和は、

sum[u,r]-sum[u,l]-sum[d,r]+sum[d,l]

で求まる。ここで、長方形を全部列挙するのではなく、ひとまずを固定してx方向の一次元の問題にする。

sum[u,r]+sum[d,l]=sum[u,l]+sum[d,r]を満たすに対し、面積はとなるので、を最大化したい。
まず、新たに長さの配列sを用意して

s[0]=0;
for (var x = 1; x <= W; x++) s[x] = sum[u, x] - sum[d, x];

とすると、sum[u,r]+sum[d,l]=sum[u,l]+sum[d,r]は、s[l]=s[r]と言い換えられる。
よって、ある値s[l]が配列の中で最後に登場するのがいつかを計算しておけばよい。
Dictionary(C++ではunordered_map)を用いれば、

var dict = new Dictionary<int, int>();
for (var x = 0; x <= W; x++) dict[s[x]] = x;

としてr=dict[s[l]]で求まる。

計算量は、を固定すると(SortedDictionary(C++のmap)なら)なので、
全体ではとなる。

ソースコード

using System;
using System.Collections.Generic;
using System.Linq;
class E { static void Main() { new K(); } }
class K
{
	int[] G() { return Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); }
	public K()
	{
		var I = G();
		int H = I[0], W = I[1];
		var C = new int[H][];
		for (var i = 0; i < H; i++) C[i] = G();
		var sum = new int[H + 1, W + 1];
		for (var i = 0; i < H; i++) for (var j = 0; j < W; j++) if ((i + j) % 2 != 0) C[i][j] *= -1;
		for (var i = 0; i < H; i++) for (var j = 0; j < W; j++) sum[i + 1, j + 1] = C[i][j] + sum[i, j + 1] + sum[i + 1, j] - sum[i, j];
		var max = 0;
		for (var d = 0; d < H; d++)
			for (var u = d + 1; u <= H; u++)
			{
				var s = new int[W + 1];
				for (var x = 1; x <= W; x++) s[x] = sum[u, x] - sum[d, x];
				var dict = new Dictionary<int, int>();
				for (var x = 0; x <= W; x++) dict[s[x]] = x;
				for (var x = 0; x <= W; x++) max = Math.Max(max, (u - d) * (dict[s[x]] - x));
			}
		Console.WriteLine(max);
	}
}