AtCoder

ABC295 B問題(Bombs)を解く

AtCoder_ABC295_B

AtCoder が提供しているABC(AtCoder Beginner Contest)295 のB問題をC++とPythonで解いてみました。ABC295は、2023年3月25日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

B問題 Bombs(Difficulty : 156)

問題はリンク先をご覧ください。

ABC295 B問題 Bombs

問題の記載に従ってプログラムで処理する問題です。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が逆転していました。

ABC295 について、引き続き、D問題まで紹介します。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA