AtCoder が提供しているABC（AtCoder Beginner Contest）363 E問題をC++とPythonで解いてみました。ABC363は、2024年7月20日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Sinking Land（Difficulty : 1307）
問題の詳細は、リンク先をご覧ください。
BFSで解きます。キューに格納する場合が2通りあります。AtCoder Problems による Difficulty は 1307 でした。
解答案
BFSを用いて、海に沈んだ区画を求めます。
C++ プログラム例（ABC363E）
map コンテナに、標高が同じ区画を格納しておきます。BFSのキューには、区画を追加します。
- 標高が 1 から $Y$ まで次の処理をします。
- その標高を持つ区画が以下の場合、キューに格納します。
- 島の端にあれば、キューに格納します（29行目）。
- 上下左右に隣接する区画が沈んでいれば、キューに格納します（37行目）。
- キューから区画を取り出して、上下左右に隣接する区画の標高が取り出した区間以下であれば、キューにその隣接区間を格納します（59行目）。
- キューに格納する毎に島の面積が1減ります。
- その標高を持つ区画が以下の場合、キューに格納します。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h, w, y;
cin >> h >> w >> y;
vector<vector<int>> a(h, vector<int>(w));
map<int, vector<pair<int, int>>> m;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cin >> a[i][j];
m[a[i][j]].push_back(make_pair(i, j));
}
}
int di[4] = {1, 0, -1, 0};
int dj[4] = {0, 1, 0, -1};
int remain = h * w;
vector<int> result(y + 1);
queue<pair<int, int>> que;
vector<vector<int>> sink(h, vector<int>(w, 0));
for (int k = 1; k <= y; ++k) {
for (auto e : m[k]) {
int ti = e.first;
int tj = e.second;
if ((ti == 0)||(ti == h - 1)||(tj == 0)||(tj == w - 1)) {
que.push(make_pair(ti, tj));
sink[ti][tj] = 1;
--remain;
} else {
for (int d = 0; d < 4; ++d) {
int next_i = ti + di[d];
int next_j = tj + dj[d];
if (sink[next_i][next_j] == 1) {
que.push(make_pair(ti, tj));
sink[ti][tj] = 1;
--remain;
break;
}
}
}
}
while (!que.empty()) {
pair<int, int> now = que.front();
que.pop();
int now_i = now.first;
int now_j = now.second;
for (int d = 0; d < 4; ++d) {
int next_i = now_i + di[d];
int next_j = now_j + dj[d];
if ((0 <= next_i)&&(next_i < h)
&&(0 <= next_j)&&(next_j < w)
&&(sink[next_i][next_j] == 0)
&&(a[next_i][next_j] <= k)) {
que.push(make_pair(next_i, next_j));
sink[next_i][next_j] = 1;
--remain;
}
}
}
result[k] = remain;
}
for (int k = 1; k <= y; ++k) {
cout << result[k] << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC363E）
Python版も基本的な考え方は同じです。
以下のプログラムは、「Python (CPython 3.11.4)」では、TLE判定となり、「Python (PyPy 3.10-v7.3.12)」で、AC判定となりました。
"""AtCoder Beginner Contest 363 E"""
from collections import defaultdict
from collections import deque
m = defaultdict(list)
h, w, y = map(int, input().split())
a = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
a[i] = list(map(int, input().split()))
for j in range(w):
m[a[i][j]].append((i, j))
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
remain = h * w
result = [0] * (y + 1)
que = deque()
sink = [[0 for _ in range(w)] for _ in range(h)]
for k in range(1, y + 1):
for e in m[k]:
ti = e[0]
tj = e[1]
if ti == 0 or ti == h - 1 or tj == 0 or tj == w - 1:
que.append((ti, tj))
sink[ti][tj] = 1
remain -= 1
else:
for d in range(4):
next_i = ti + di[d]
next_j = tj + dj[d]
if sink[next_i][next_j] == 1:
que.append((ti, tj))
sink[ti][tj] = 1
remain -= 1
break
while que:
now = que.popleft()
now_i = now[0]
now_j = now[1]
for d in range(4):
next_i = now_i + di[d]
next_j = now_j + dj[d]
if 0 <= next_i < h and 0 <= next_j < w and \
sink[next_i][next_j] == 0 and a[next_i][next_j] <= k:
que.append((next_i, next_j))
sink[next_i][next_j] = 1
remain -= 1
result[k] = remain
for i in range(1, k + 1):
print(result[i])最後に
この問題は、コンテスト中に解けた問題としては最大Diffでした。コンテストも、過去最高のパフォーマンスと評価されました。このようなことがあるとうれしくなります。
引き続き ABC の問題を紹介していきます。
