AtCoder が提供しているABC（AtCoder Beginner Contest）341 のC問題をC++とPythonで解いてみました。ABC341は、2024年2月17日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Takahashi Gets Lost（Difficulty : 406）
問題はリンク先をご覧ください。
ABC341 C問題 Takahashi Gets Lost
陸となっているグリッドを全探索します。AtCoder Problems による Difficulty は 406 でした。
解答案
問題の設定に従い、すべての陸となるグリッドを出発点として、文字列に従い陸を移動できるか調べます。
C++ プログラム例（ABC341C）
陸であるグリッドから、文字列Tに従い移動します。通過するグリッドがすべて陸なら変数 result の値を増やします。すべての陸のグリッドを調べて、最後に result を出力します。
問題の制約で外周が海で囲まれています。このため、範囲外になる前に海に出ます。これによりプログラムは楽になっています。もし、外周にこのような制約がない場合は、自分で門番として設定することにより、同じようにプログラムをすっきりと書くことができます。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h, w, n;
cin >> h >> w >> n;
string t;
cin >> t;
vector<string> s(h);
for (int i = 0; i < h; ++i) {
cin >> s[i];
}
int result = 0;
for (int i = 1; i < h - 1; ++i) {
for (int j = 1; j < w - 1; ++j) {
if (s[i][j] == '#') {
continue;
}
int ni = i;
int nj = j;
bool is_ok = true;
for (int k = 0; k < n; ++k) {
if (t[k] == 'L') {
--nj;
} else if (t[k] == 'R') {
++nj;
} else if (t[k] == 'U') {
--ni;
} else if (t[k] == 'D') {
++ni;
}
if (s[ni][nj] == '#') {
is_ok = false;
break;
}
}
if (is_ok){
++result;
}
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC341C）
Python 版も基本的な考え方は同じです。
以下のプログラムは、「Python (CPython 3.11.4)」では、TLE判定となり、「Python (PyPy 3.10-v7.3.12)」で、AC判定となりました。
"""AtCoder Beginner Contest 341 C"""
h, w, n = map(int, input().split())
t = input()
s = [input() for i in range(h)]
result = 0
for i in range(1, h - 1):
for j in range(1, w - 1):
if s[i][j] == '#':
continue
ni = i
nj = j
is_ok = True
for k in range(n):
if t[k] == 'L':
nj -= 1
elif t[k] == 'R':
nj += 1
elif t[k] == 'U':
ni -= 1
elif t[k] == 'D':
ni += 1
if s[ni][nj] == '#':
is_ok = False
break
if is_ok:
result += 1
print(result)こちらも「AC」と判定されました。
最後に
制約から計算量が $O(HWN)=5 \times 10^2 \times 5 \times 10^2 \times 5 \times 10^2 = 1.25 \times 10^8$ と心配になる大きさとなりました。
言語によっては、TLEとなるかもしれません。事実 CPython では TLE でした。このような計算量の場合は、C++ は有利に感じます。
引き続き ABC の問題を紹介していきます。
