AtCoder

ABC300 C問題(Cross)を解く

AtCoder_ABC300_C

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

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

C問題 Cross(Difficulty : 534)

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

ABC300 C問題 Cross

与えられたグリッドの中にある特定の形を探す問題です。AtCoder Problems による Difficulty は 534 でした。

解答案

与えられたグリッドに含まれている「×」の字を探します。以下の制約があります。

  • 「×」の字を構成する文字 ‘#’ は、すべて「×」に含まれています。
  • それぞれの「×」の字は隣接していません。

C++ プログラム例(ABC300C)

文字 ‘#’ を見つけたら、関数 check を呼び出します。この関数は斜め4方向を調べて、「×」の字の長さを返します。関数の戻り値を配列 result に格納します。

関数 check では、一時変数 _n に対して斜め4方向を調べて、4方向に ‘#’ があるばあいに、変数 n を更新しています。配列内へのアクセスチェックをする条件は少し長くなりました。

以下が、C++プログラムとなります。

#include <bits/stdc++.h>
using namespace std;

int h, w;
vector<string> c;

int check(int i, int j)
{
	int n = 0;
	while (true) {
		int _n = n + 1;
		if (!((i + _n < h)&&(j + _n < w)&&(c[i + _n][j + _n] == '#'))) {
			break;
		}
		if (!((i + _n < h)&&(j - _n >= 0)&&(c[i + _n][j - _n] == '#'))) {
			break;
		}
		if (!((i - _n >= 0)&&(j + _n < w)&&(c[i - _n][j + _n] == '#'))) {
			break;
		}
		if (!((i - _n >= 0)&&(j - _n >= 0)&&(c[i - _n][j - _n] == '#'))) {
			break;
		}
		++n;
	}

	return n;
}

int main()
{
	cin >> h >> w;
	c.resize(h);
	for (int i = 0; i < h; ++i) {
		cin >> c[i];
	}

	int n = min(h, w);
	vector<int> result(n + 1, 0);
	for (int i = 1; i < h - 1; ++i) {
		for (int j = 1; j < w - 1; ++j) {
			if (c[i][j] == '#') {
				++result[check(i, j)];
			}
		}
	}

	for (int i = 1; i <= n; ++i) {
		cout << result[i] << " \n"[i == n];
	}

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC300C)

C++のロジックをそのまま Python に書き直しました。結果を格納するリスト result は、添え字が1以上の場合のみ出力するため、スライス表記を使っています(29行目)。

"""AtCoder Beginner Contest 300 C"""


def check(i, j):
    n = 0
    while True:
        _n = n + 1
        if not (i + _n < h and j + _n < w and c[i + _n][j + _n] == '#'):
            break
        if not (i + _n < h and j - _n >= 0 and c[i + _n][j - _n] == '#'):
            break
        if not (i - _n >= 0 and j + _n < w and c[i - _n][j + _n] == '#'):
            break
        if not (i - _n >= 0 and j - _n >= 0 and c[i - _n][j - _n] == '#'):
            break
        n += 1

    return n


h, w = map(int, input().split())
c = [input() for i in range(h)]

n = min(h, w)
result = [0] * (n + 1)
for i in range(1, h - 1):
    for j in range(1, w - 1):
        if c[i][j] == '#':
            result[check(i, j)] += 1

print(*result[1:])

こちらも「AC」と判定されました。

最後に

この問題は、特定のアルゴリズムの知識が無くても解くことができます。その一方、配列の範囲内チェックが必要であったり、条件も多いため、プログラミングに注意が必要な問題でした。

ABC300 について、引き続き問題を紹介していきます。

COMMENT

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

CAPTCHA