AtCoder が提供しているABC（AtCoder Beginner Contest）318 のB問題をC++とPythonで解いてみました。ABC318は、2023年9月2日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Overlapping sheets（Difficulty : 101）
問題はリンク先をご覧ください。
シートがある場所をメモに残して、まとめて集計します。AtCoder Problems による Difficulty は 101 でした。
解答案
各シートの情報 a、b、c、d を読み込みます。2次元配列 t [x][y] に対して、 $a \leqq x < b, \;c \leqq y < d$ の要素の値に1を加えます。$N$ 枚の処理が終わった後、t[x][y] の値が 0 より大きい配列の要素の個数が面積となります。
C++ プログラム例（ABC318B）
上記の考察をプログラムに変換します。
- t[x][y] の値を更新する（12ー14行目）。
- t[x][y] > 0 の要素をカウントする（20－23行目）。
- カウントした値を出力する（28行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<vector<int>> t(100, vector<int>(100, 0));
for (int i = 0; i < n; ++i) {
int a, b, c, d;
cin >> a >> b >> c >> d;
for (int x = a; x < b; ++x) {
for (int y = c; y < d; ++y) {
++t[x][y];
}
}
}
int result = 0;
for (int i = 0; i < 100; ++i) {
for (int j = 0; j < 100; ++j) {
if (t[i][j] > 0) {
++result;
}
}
}
cout << result << endl;
return 0;
}（参考）いもす法
2次元のいもす法と呼ばれる方法でも解くことができます。最終的に計算で得られる配列 t は同じ値になります。ただし、こちらの方が計算量は少なくなります。詳しくはいもす法（もしくは、imos法）で検索してください。
キーとなるコードの背景色を変更しています。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<vector<int>> t(101, vector<int>(101, 0));
for (int i = 0; i < n; ++i) {
int a, b, c, d;
cin >> a >> b >> c >> d;
++t[a][c];
--t[a][d];
--t[b][c];
++t[b][d];
}
for (int i = 0; i < 101; ++i) {
for (int j = 0; j < 100; ++j) {
t[i][j + 1] += t[i][j];
}
}
for (int i = 0; i < 100; ++i) {
for (int j = 0; j < 101; ++j) {
t[i + 1][j] += t[i][j];
}
}
int result = 0;
for (int i = 0; i < 100; ++i) {
for (int j = 0; j < 100; ++j) {
if (t[i][j] > 0) {
++result;
}
}
}
cout << result << endl;
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC318B）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 318 B"""
n = int(input())
t = [[0 for j in range(100)] for i in range(100)]
for i in range(n):
a, b, c, d = map(int, input().split())
for x in range(a, b):
for y in range(c, d):
t[x][y] += 1
result = 0
for i in range(100):
for j in range(100):
if t[i][j] > 0:
result += 1
print(result)こちらも「AC」と判定されました。
最後に
このB問題は、いもす法で解きました。B問題でACを得たのは、20分47秒でした。いもす法で解くときに配列をひとつ多く確保することを忘れて時間を失いました。ABC318A問題でも反省しましたが、計算時間が間に合う場合は、平易な方法で解いた方がよいかもしれません。
引き続き ABC の問題を紹介していきます。
