AtCoder が提供しているABC（AtCoder Beginner Contest）291 のC問題をC++とPythonで解いてみました。ABC291は、2023年2月26日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 LRUD Instructions 2（Difficulty : 188）
問題はリンク先をご覧ください。
ABC291 C問題 LRUD Instructions 2
set で管理する座標を文字列に従い計算していきます。AtCoder Problems による Difficulty は 188 でした。
解答案
問題を以下の方針で解きます。
- N と文字列 S を読み込む。
- 座標の初期値を (0, 0) とする。
- 解答フラグを false にする。
- 文字列が含む文字に従い、以下を行う。
- RLUDに従い座標を動かす。
- 移動先の座標がすでに訪れていた場合は、解答フラグを true にする。
- 解答フラグに従い、”Yes” もしくは “No” を出力する。
C++ プログラム例（ABC291C）
訪れたことがある座標を set コンテナで管理します。移動先の座標が格納済であれば、変数 result を true にします。移動先の座標が格納されていないなら、格納します。
文字の判定は、if – else if 文ではなく、switch 文を使いました。C++ の switch 文の各 case 節には、break が必要となるのは注意です。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
string s;
cin >> s;
int x = 0;
int y = 0;
bool result = false;
set<pair<int, int>> p;
p.insert(make_pair(0, 0));
for (int i = 0; i < n; ++i) {
switch (s[i]) {
case 'R':
++x;
break;
case 'L':
--x;
break;
case 'U':
++y;
break;
case 'D':
--y;
break;
}
if (p.find(make_pair(x, y)) == p.end()) {
p.insert(make_pair(x, y));
} else {
result = true;
}
}
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC291C）
Python でも set を使います。書いてあるロジックは、C++ 版とほぼ同じです。
"""AtCoder Beginner Contest 291 C"""
n = int(input())
s = input()
x, y = 0, 0
result = False
p = set()
p.add((0, 0))
for i, ch in enumerate(s):
if ch == 'R':
x += 1
if ch == 'L':
x -= 1
if ch == 'U':
y += 1
if ch == 'D':
y -= 1
if (x, y) not in p:
p.add((x, y))
else:
result = True
print("Yes" if result else "No")こちらも「AC」と判定されました。
最後に
訪れたかを set で管理することによって判断することが思い浮かべば解ける問題でした。
引き続き ABC の問題を紹介していきます。
