AtCoder

ABC335 C問題(Loong Tracking)を解く

AtCoder_ABC335_C

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

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

C問題 Loong Tracking(Difficulty : 452)

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

ABC335 C問題 Loong Tracking

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 の問題を紹介していきます。

COMMENT

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

CAPTCHA