AtCoder

ABC303 C問題(Dash)を解く

AtCoder_ABC303_C

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

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

C問題 Dash(Difficulty : 417)

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

ABC303 C問題 Dash

set コンテナを使って、与えられた文字列に従いシミュレートします。AtCoder Problems による Difficulty は 417 でした。

解答案

B問題に続き set コンテナを使います。

B問題は、配列で処理することができましたが、この問題は、$|x_i|, |y_i| \leqq 2 \times 10^5$ と $(x_i, y_i)$ の配列が大きくなりすぎて用意することできません。set コンテナを学ぶことができる良い問題だと思います。

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

アイテムの座標を set コンテナ item に insert していきます(14行目)。

文字列の1文字1文字について、以下の操作を行います。

  • “RLUD” に従い、座標 (x, y) を更新する。
  • 体力 h を 1 減らす。
  • 体力 h が負になった場合、result を false に設定して break する。
  • (x, y) にアイテムがあり、体力 h < K であれば、h = K として、アイテムを削除する。

以下が、C++プログラムとなります。set コンテナに関する行の背景色を変更しています。

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

int main()
{
	int n, m, h, k;
	cin >> n >> m >> h >> k;
	string s;
	cin >> s;
	set<pair<int, int>> item;
	for (int i = 0; i < m; ++i) {
		int x, y;
		cin >> x >> y;
		item.insert(make_pair(x, y));
	}

	bool result = true;
	int x = 0;
	int y = 0;
	for (int i = 0; i < n; ++i) {
		if (s[i] == 'R') {
			++x;
		} else if (s[i] == 'L') {
			--x;
		} else if (s[i] == 'U') {
			++y;
		} else if (s[i] == 'D') {
			--y;
		}
		--h;

		if (h < 0) {
			result = false;
			break;
		}
		if (item.find(make_pair(x, y)) != item.end()) {
			if (h < k) {
				h = k;
				item.erase(make_pair(x, y));
			}
		}
	}

	if (result) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}

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

Python プログラム例(ABC303C)

Python 版も C++ 版のプログラムをそのまま移植しました。細かな差ですが、文字列の走査は、enumerate を使うことを pylint が推奨しています(11行目)。

"""AtCoder Beginner Contest 303 C"""
n, m, h, k = map(int, input().split())
s = input()
item = set()
for i in range(m):
    xt, yt = map(int, input().split())
    item.add((xt, yt))

result = True
x, y = 0, 0
for _, ch in enumerate(s):
    if ch == 'R':
        x += 1
    elif ch == 'L':
        x -= 1
    elif ch == 'U':
        y += 1
    elif ch == 'D':
        y -= 1
    h -= 1

    if h < 0:
        result = False
        break
    if (x, y) in item:
        if h < k:
            h = k
            item.remove((x, y))

print("Yes" if result else "No")

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

最後に

体力が K に戻ったときにアイテムを削除することを忘れていました。そのため、1回WA(Wrong Answer)判定となりました。WA判定により、アイテムを削除することを忘れていたことに気づきました。今後、似たような条件漏れに気づけるようになればと思います。

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

COMMENT

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

CAPTCHA