AtCoder が提供しているABC（AtCoder Beginner Contest）335 のC問題をC++とPythonで解いてみました。ABC335は、2024年1月6日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Loong Tracking（Difficulty : 452）
問題はリンク先をご覧ください。
Deque または可変配列を使います。AtCoder Problems による Difficulty は 452 でした。
解答案
C++ プログラム例（ABC335C）
C++では、Deque（Double-Ended QUEue）コンテナを使います。このコンテナは、先頭および末尾への要素の追加、削除、インデックスによるアクセスが高速に動作します。Deque コンテナについては、この記事で紹介しています。
- 初期値を Deque コンテナ pos に格納します。
- クエリを処理します。
- クエリ1の場合、pos の先頭 pos[0] の場所を元に頭の位置を更新して、その場所を push_front でコンテナの先頭に格納します。（削除する必要はないですが）最後の要素を pop_back で削除しておきます。
- クエリ2の場合、添え字でアクセスして、場所を出力します。pos の添え字は0から、問題は1からカウントするため、添え字の値をデクリメントしています。
結果的に deque コンテナを素直に使うだけで解くことができました。以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, q;
cin >> n >> q;
deque<pair<int, int>> pos(n);
for (int i = 0; i < n; ++i) {
pos[i] = make_pair(i + 1, 0);
}
for (int i = 0; i < q; ++i) {
int type;
cin >> type;
if (type == 1) {
char c;
cin >> c;
int x = pos[0].first;
int y = pos[0].second;
if (c == 'R') {
x += 1;
} else if (c == 'L') {
x -= 1;
} else if (c == 'U') {
y += 1;
} else if (c == 'D') {
y -= 1;
}
pos.push_front(make_pair(x, y));
pos.pop_back();
} else if (type == 2) {
int p;
cin >> p;
--p;
cout << pos[p].first << " " << pos[p].second << endl;
}
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC335C）
Python 版も deque が提供されているため、同じように実装します。
"""AtCoder Beginner Contest 335 C"""
from collections import deque
n, q = map(int, input().split())
pos = deque()
for i in range(n):
pos.append((i + 1, 0))
for i in range(q):
query = list(input().split())
t = int(query[0])
if t == 1:
c = query[1]
x = pos[0][0]
y = pos[0][1]
if c == 'R':
x += 1
elif c == 'L':
x -= 1
elif c == 'U':
y += 1
elif c == 'D':
y -= 1
pos.appendleft((x, y))
pos.pop()
elif t == 2:
p = int(query[1])
p -= 1
print(*pos[p])
残念ながらこのプログラムは、TLE（Time Limit Exceeded）と判定されました。
Python の deque は、append、appendleft、pop は、$O(1)$ で動作するようですが、[] を使ったアクセスは、$O(n)$ となります。一方、リストでは、先頭への要素の追加 insert(0, value) の計算量が $O(n)$ となり、こちらも間に合いません。
上記から、リストに位置を逆順に格納することにします（3ー5行目）。最後の要素（頭の位置）を取り出して、更新して、append で末尾に追加します（22行目）。アクセスは、[- インデックス] で値を取り出せます。この場合、1からカウントするため、デクリメントする必要がありません。以下となります。
"""AtCoder Beginner Contest 335 C"""
n, q = map(int, input().split())
pos = []
for i in range(n, 0, -1):
pos.append((i, 0))
for i in range(q):
query = list(input().split())
t = int(query[0])
if t == 1:
c = query[1]
x = pos[-1][0]
y = pos[-1][1]
if c == 'R':
x += 1
elif c == 'L':
x -= 1
elif c == 'U':
y += 1
elif c == 'D':
y -= 1
pos.append((x, y))
elif t == 2:
p = int(query[1])
print(*pos[-p])こちらは「AC」と判定されました。
最後に
C++の deque は、リング状のバッファを使っていると思われます。一方、Python の deque は、双方向リストを使っていると思われます。言語によりコンテナの実装が異なるようです。勉強になりました。
引き続き ABC の問題を紹介していきます。
