AtCoder が提供しているABC（AtCoder Beginner Contest）311 のE問題をC++とPythonで解いてみました。ABC311は、2023年7月22日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Defect-free Squares（Difficulty : 1293）
問題はリンク先をご覧ください。
ABC311 E問題 Defect-free Squares
正方形の右下座標に注目してDPを使います。AtCoder Problems による Difficulty は 1293 でした。
解答案
正方形の右下に注目してDPで解くことができます。
dp[i][j] は、(i, j) を右下とする最大の穴のない正方形の辺の長さとします。グリッド内の穴のない正方形の数は、縦 $1 \leqq i \leqq H$、横 $1 \leqq j \leqq W$ の範囲で dp[i][j] の値の総和となります。
漸化式は以下となります。
dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
この漸化式を分かりやすく説明しているページがありました。最大の正方形の大きさを求めていますが、本質的な考えは同じです。たいへん参考になりました。
最大正方形の面積の求め方を知ってますか？ 2次元の動的計画法（貰う/配る）をビジュアライズしてみました！
C++ プログラム例（ABC311E）
右下に穴がないことを確認して、漸化式に従い dp を更新します（24行目）。最終的な解答となる変数 result は、更新した dp の値を加えていきます（25行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
int h, w, n;
cin >> h >> w >> n;
set<pair<int, int>> ab;
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
ab.insert(make_pair(a, b));
}
vector<vector<int>> dp(h + 1, vector<int>(w + 1, 0));
ull result = 0;
for (int i = 1; i <= h; ++i) {
for (int j = 1; j <= w; ++j) {
if (ab.find(make_pair(i, j)) != ab.end()) {
continue;
}
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
result += dp[i][j];
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC311E）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 311 E"""
h, w, n = map(int, input().split())
ab = set()
for i in range(n):
a, b = map(int, input().split())
ab.add((a, b))
dp = [[0 for _ in range(w + 1)] for _ in range(h + 1)]
result = 0
for i in range(1, h + 1):
for j in range(1, w + 1):
if (i, j) in ab:
continue
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
result += dp[i][j]
print(result)こちらも「AC」と判定されました。
最後に
この問題は、コンテストでは解くことができませんでした。コンテスト後に公式解説を読み理解ができました。問題としては、典型のようです。AOJ で同じ趣旨の問題が紹介されていました。
DPL 組み合わせ最適化 3_A: Largest Square
このような典型問題を習得して、実力を上げていきたいです。
引き続き ABC の問題を紹介していきます。
