AtCoder が提供しているABC（AtCoder Beginner Contest）383 B問題をC++とPythonで解いてみました。ABC383は、2024年12月7日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Humidifier 2（Difficulty : 272）
問題の詳細は、リンク先をご覧ください。
床の場所を特定して全探索します。AtCoder Problems による Difficulty は 272 でした。
解答案
C++ プログラム例（ABC383B）
B問題としては実装が少し長くなりました。
- 床の位置を配列
fに格納します（18ー25行目）。 - 異なる床を2か所（
h1、h2）選び、それらとすべての床とのマンハッタン距離が d 以下かを調べます。マンハッタン距離は別関数diffで求めます。 - 加湿できる床の最大値
resultを更新します（36行目）。
床の数は最大 $H \times W=100$ 個であり、計算量は $100^3 = 10^6$ となるため、全探索で解くことが可能です。以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int diff(pair<int, int> p1, pair<int, int> p2)
{
return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}
int main()
{
int h, w, d;
cin >> h >> w >> d;
vector<string> s(h);
for (int i = 0; i < h; ++i) {
cin >> s[i];
}
vector<pair<int, int>> f;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (s[i][j] == '.') {
f.push_back(make_pair(i, j));
}
}
}
int result = 0;
for (int h1 = 0; h1 < (int)f.size(); ++h1) {
for (int h2 = h1 + 1; h2 < (int)f.size(); ++h2) {
int t_result = 0;
for (int f3 = 0; f3 < (int)f.size(); ++f3) {
if ((diff(f[f3], f[h1]) <= d) || (diff(f[f3], f[h2]) <= d)) {
++t_result;
}
}
result = max(result, t_result);
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC383B）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 383 B"""
def diff(p1, p2):
return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
h, w, d = map(int, input().split())
s = [input() for i in range(h)]
f = []
for i in range(h):
for j in range(w):
if s[i][j] == '.':
f.append((i, j))
result = 0
for h1 in range(len(f)):
for h2 in range(h1 + 1, len(f)):
t_result = 0
for f3 in f:
if diff(f3, f[h1]) <= d or diff(f3, f[h2]) <= d:
t_result += 1
result = max(result, t_result)
print(result)こちらも「AC」と判定されました。
最後に
この問題は全探索で解くことが可能でした。
引き続き ABC の問題を紹介していきます。
