AtCoder が提供しているABC（AtCoder Beginner Contest）303 のC問題をC++とPythonで解いてみました。ABC303は、2023年5月27日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Dash（Difficulty : 417）
問題はリンク先をご覧ください。
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判定により、アイテムを削除することを忘れていたことに気づきました。今後、似たような条件漏れに気づけるようになればと思います。
引き続き ABC の問題を紹介していきます。
