AtCoder が提供しているABC（AtCoder Beginner Contest）005 D問題をC++で解いてみました。ABC005は、2014年3月22日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 おいしいたこ焼きの焼き方（Difficulty : 1447（参考値））
問題の詳細は、リンク先をご覧ください。
2次元の累積和を求めて準備しておきます。AtCoder Problems による Difficulty は 1447（参考値）でした。
解答案
C++ プログラム例（ABC005D）
たこ焼き器内のすべての長方形領域について、美味しさを事前に計算しておくことで、計算量を削減できます。このために2次元の累積和を利用します。
プログラムの補足です。
- 2次元の累積和を計算します（15ー23行目）。
- 累積和を用いて、すべての部分長方形の面積に対する美味しさの最大値
mを計算します（25ー36行目）。 - その面積より小さい面積が持つ美味しさの最大値で、その面積の美味しさの最大値を更新します（38ー42行目）。
- 各店員が焼けるたこ焼きの最大美味しさを出力します（49行目）。
以下が、C++プログラムです。累積和の定番コードの背景色を変更しました。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<vector<int>> d(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> d[i][j];
}
}
vector<vector<int>> sum_d(n + 1, vector<int>(n + 1, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
sum_d[i + 1][j + 1] = sum_d[i][j + 1];
sum_d[i + 1][j + 1] += sum_d[i + 1][j];
sum_d[i + 1][j + 1] -= sum_d[i][j];
sum_d[i + 1][j + 1] += d[i][j];
}
}
vector<int> m(50 * 50 * 1000 + 1, 0);
for (int i1 = 0; i1 < n; ++i1) {
for (int i2 = i1 + 1; i2 <= n; ++i2) {
for (int j1 = 0; j1 < n; ++j1) {
for (int j2 = j1 + 1; j2 <= n; ++j2) {
int t = sum_d[i2][j2] - sum_d[i1][j2] - sum_d[i2][j1] +
sum_d[i1][j1];
m[(i2 - i1) * (j2 - j1)] = max(m[(i2 - i1) * (j2 - j1)], t);
}
}
}
}
int d_max = 0;
for (int i = 0; i <= 50 * 50 * 1000; ++i) {
d_max = max(m[i], d_max);
m[i] = d_max;
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int p;
cin >> p;
cout << m[p] << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
2次元の累積和は、基本的には1次元の累積和と同じ原理ですが、式が複雑に感じられます。テンプレートを活用して解決しました。
引き続き ABC の問題を紹介していきます。
