AtCoder が提供しているABC（AtCoder Beginner Contest）383 C問題をC++とPythonで解いてみました。ABC383は、2024年12月7日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Humidifier 3（Difficulty : 750）
問題の詳細は、リンク先をご覧ください。
BFS で床の間の最短距離を求めます。工夫が必要です。AtCoder Problems による Difficulty は 750 でした。
解答案
コンテスト中、最初に以下のプログラムを提出しました。以下は補足です。
- グリッド間の最短距離は、BFS で計算します。
- 各マスが床であれば、その床から距離 $d$ 以下の床を set コンテナ
resultに格納します。set コンテナに格納しているため、重複を避けることができます。 - 最後に
resultの大きさを出力します。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h, w, d;
cin >> h >> w >> d;
vector<string> s(h);
for (int i = 0; i < h; ++i) {
cin >> s[i];
}
int di[4] = {1, 0, -1, 0};
int dj[4] = {0, 1, 0, -1};
set<pair<int, int>> result;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (s[i][j] != 'H') {
continue;
}
result.insert(make_pair(i, j));
queue<pair<int, int>> que;
vector<vector<int>> dist(h, vector<int>(w, -1));
que.push(make_pair(i, j));
dist[i][j] = 0;
while (!que.empty()) {
pair<int, int> now = que.front();
que.pop();
int now_i = now.first;
int now_j = now.second;
for (int dir = 0; dir < 4; ++dir) {
int next_i = now_i + di[dir];
int next_j = now_j + dj[dir];
if ((0 <= next_i) && (next_i < h) && (0 <= next_j) &&
(next_j < w) && (dist[next_i][next_j] == -1) &&
(s[next_i][next_j] != '#')) {
dist[next_i][next_j] = dist[now_i][now_j] + 1;
if (dist[next_i][next_j] <= d) {
que.push(make_pair(next_i, next_j));
result.insert(make_pair(next_i, next_j));
}
}
}
}
}
}
cout << result.size() << endl;
return 0;
}42テストケースのうち、16テストケースで TLE（Time Limit Exceed）となりました。加湿器ごとにキューを用いた最短距離の走査を行っているためです。
C++ プログラム例（ABC383C）
キューにすべての加湿器を格納し、残りの床との最短距離を求めます。この手順であれば、キューによる走査は一度で済みます。TLE となったプログラムから以下を変更します。
- キューにすべての加湿器を格納します（18ー27行目）。
- BFS で加湿器から床との距離を求めます（28ー44行目）。
- 加湿器から距離が
d以下の床の個数を求めます（46ー53行目）。
以下が、C++プログラムです。AC（Accepted＝正しいプログラム）と判定されました。
#include <bits/stdc++.h>
using namespace std;
#define INF (1 << 30)
int main()
{
int h, w, d;
cin >> h >> w >> d;
vector<string> s(h);
for (int i = 0; i < h; ++i) {
cin >> s[i];
}
int di[4] = {1, 0, -1, 0};
int dj[4] = {0, 1, 0, -1};
queue<pair<int, int>> que;
vector<vector<int>> dist(h, vector<int>(w, INF));
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (s[i][j] == 'H') {
que.push(make_pair(i, j));
dist[i][j] = 0;
}
}
}
while (!que.empty()) {
pair<int, int> now = que.front();
que.pop();
int now_i = now.first;
int now_j = now.second;
for (int dir = 0; dir < 4; ++dir) {
int next_i = now_i + di[dir];
int next_j = now_j + dj[dir];
if ((0 <= next_i) && (next_i < h) && (0 <= next_j) &&
(next_j < w) && (dist[next_i][next_j] == INF) &&
(s[next_i][next_j] != '#')) {
que.push(make_pair(next_i, next_j));
dist[next_i][next_j] = dist[now_i][now_j] + 1;
}
}
}
int result = 0;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (dist[i][j] <= d) {
++result;
}
}
}
cout << result << endl;
return 0;
}Python プログラム例（ABC383C）
Python版も基本的な考え方は同じです。キューは、collections.deque を使いました。以下がプログラムです。
"""AtCoder Beginner Contest 383 C"""
from collections import deque
INF = (1 << 30)
h, w, d = map(int, input().split())
s = [input() for i in range(h)]
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
que = deque()
dist = [[INF for _ in range(w)] for _ in range(h)]
for i in range(h):
for j in range(w):
if s[i][j] == 'H':
que.append((i, j))
dist[i][j] = 0
while que:
now_i, now_j = que.popleft()
for direction in range(4):
next_i = now_i + di[direction]
next_j = now_j + dj[direction]
if 0 <= next_i < h and 0 <= next_j < w and \
dist[next_i][next_j] == INF and s[next_i][next_j] != '#':
que.append((next_i, next_j))
dist[next_i][next_j] = dist[now_i][now_j] + 1
result = 0
for i in range(h):
for j in range(w):
if dist[i][j] <= d:
result += 1
print(result)こちらも「AC」と判定されました。
最後に
公式解説では、「多始点 bfs」と紹介されていました。学ぶことができました。
引き続き ABC の問題を紹介していきます。
