AtCoder が提供しているABC（AtCoder Beginner Contest）295 のB問題をC++とPythonで解いてみました。ABC295は、2023年3月25日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Bombs（Difficulty : 156）
問題はリンク先をご覧ください。
問題の記載に従ってプログラムで処理する問題です。AtCoder Problems による Difficulty は 156 でした。
解答案
問題の記載に従って、爆弾を処理していきます。処理する内容をまとめます。
- 爆弾（数字）が爆発すると、マンハッタン距離が数字内の壁が空きマスになる。
- すべての爆弾は同時に爆発する。
C++ プログラム例（ABC295B）
処理する内容に従い爆弾を処理します。注意としてある爆弾の爆発範囲に別の爆弾がある場合、それを空きマスにしてはいけません。これは入力例3の場合が該当します。
プログラムとしては、以下となります。
- 爆発範囲にある壁は空きマスにする。ただし、爆弾（数字）はそのままにする。
- 後で、爆弾（数字）を空きマスにする。
少し長いプログラムとなりました。以下が、C++プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int r, c;
cin >> r >> c;
vector<string> b(r);
for (int i = 0; i < r; ++i) {
cin >> b[i];
}
for (int y1 = 0; y1 < r; ++y1) {
for (int x1 = 0; x1 < c; ++x1) {
if (isdigit(b[y1][x1])) {
int num = b[y1][x1] - '0';
for (int y2 = y1 - num; y2 <= y1 + num; ++y2) {
for (int x2 = x1 - num; x2 <= x1 + num; ++x2) {
if ((0 <= y2)&&(y2 < r)&&(0 <= x2)&&(x2 < c)
&&(abs(y2 - y1) + abs(x2 - x1) <= num)
&&(b[y2][x2] == '#')) {
b[y2][x2] = '.';
}
}
}
}
}
}
for (int y1 = 0; y1 < r; ++y1) {
for (int x1 = 0; x1 < c; ++x1) {
if (isdigit(b[y1][x1])) {
b[y1][x1] = '.';
}
}
}
for (int i = 0; i < r; ++i) {
cout << b[i] << endl;
}
return 0;
}上記プログラムをコンテストで提出しました。3段目と4段目の for 文はループ数を減らせていますが、if 文の判断式が複雑になっています。
以下の2点を改善しました。
- 3段目と4段目の for 文のループ数を広めにとり、if 文の判断式を簡単にしました。
- 爆発した場所を配列 finished に格納して、後で処理をしています。
改善版のプログラムは以下となります。変更点の背景色を変更しました。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int r, c;
cin >> r >> c;
vector<string> b(r);
for (int i = 0; i < r; ++i) {
cin >> b[i];
}
vector<vector<bool>> finished(r, vector<bool>(c, false));
for (int y1 = 0; y1 < r; ++y1) {
for (int x1 = 0; x1 < c; ++x1) {
if (isdigit(b[y1][x1])) {
int num = b[y1][x1] - '0';
for (int y2 = 0; y2 < r; ++y2) {
for (int x2 = 0; x2 < c; ++x2) {
if (abs(y2 - y1) + abs(x2 - x1) <= num) {
finished[y2][x2] = true;
}
}
}
}
}
}
for (int y1 = 0; y1 < r; ++y1) {
for (int x1 = 0; x1 < c; ++x1) {
if (finished[y1][x1]) {
b[y1][x1] = '.';
}
}
}
for (int i = 0; i < r; ++i) {
cout << b[i] << endl;
}
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC295B）
C++版の後者のプログラムを移植しました。Python は、文字列型の変数の上書きができないため、解答用の文字列型の変数 result に結果を格納していきます。
"""AtCoder Beginner Contest 295 B"""
r, c = map(int, input().split())
b = [input() for i in range(r)]
finished = [[False for i in range(c)] for j in range(r)]
for y1 in range(r):
for x1 in range(c):
if b[y1][x1].isdigit():
num = int(b[y1][x1])
for y2 in range(r):
for x2 in range(c):
if abs(y2 - y1) + abs(x2 - x1) <= num:
finished[y2][x2] = True
result = [""] * r
for y1 in range(r):
for x1 in range(c):
if finished[y1][x1] or b[y1][x1] == ".":
result[y1] += "."
else:
result[y1] += "#"
for y1 in range(r):
print(result[y1])こちらも「AC」と判定されました。
最後に
この問題は、すべての爆弾が同時に爆発する、という制約があり、それをどのように処理するのかがポイントとなります。4重ループの実装量も多く、C問題（122）とDifficultyが逆転していました。
引き続き ABC の問題を紹介していきます。
