【AtCoder】ABC 335 C - Loong Tracking | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 452

問題概要

から までの番号が付いた 個のパーツからなる龍を座標平面上で操作することを考える。なお、パーツ を「頭」と呼ぶ。最初、パーツ は点 にある。以下の 個のクエリを処理せよ。

• 1 c : 頭を方向 に 移動させる。 はR( 軸正方向), L( 軸負方向), U( 軸正方向), D ( 軸負方向) のいずれかであり、頭以外の全てのパーツは前のパーツに追従するように動く (パーツ は移動前にパーツ があった場所に移動する) 。
• 2 p : パーツ の座標を求める。

制約

• 入力数値はすべて整数。
• 
• 
• 

考察

全部で 個のクエリが飛んでくるので、各クエリをなるべく定数時間で処理できるように考えていく。説明の都合上、先にクエリ2から見ていく。

クエリ2について

各パーツの座標を出力しなければならないので、 それらを保持しておく配列を用意すればよいだろう。

クエリ1について

1回の移動ごとに全てのパーツの座標を1つずつ更新していては、とても実行時間制限には間に合わない。

ここで注目したいのが、「パーツ は移動前にパーツ があった場所に移動する」という条件だ。つまり、通過した座標のデータはそのままに、データを参照する範囲を移動ごとにずらしていくイメージで考えていくと良さそう。

したがってやりたいこととしては、

• 頭のパーツが通過した座標データを挿入する。
• 直前にパーツ がいた座標データを削除する。
• 任意のパーツの座標を取得する。

の3つである。配列の 番目の要素にパーツ の座標データを入れるとすると、「先頭にデータを挿入する」「末尾のデータを削除する」という操作を高速に行えるようなデータ構造が必要になる。

そんな便利なデータ構造が C++ にはdequeというもので用意されている。これを使うことで、前述の操作をどちらも定数時間で処理できる。実装方法は以下のコードを参照のこと。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

struct Position
{
    int x;
    int y;
};

int main()
{
    int N, Q;
    cin >> N >> Q;

    deque<Position> deq;
    rep(i, 1, N + 1) deq.push_back({i, 0});

    rep(q, 0, Q)
    {
        int x;
        cin >> x;

        if (x == 1)
        {
            char C;
            cin >> C;

            Position pos = deq.front();

            if (C == 'R')
                deq.push_front({pos.x + 1, pos.y});
            else if (C == 'L')
                deq.push_front({pos.x - 1, pos.y});
            else if (C == 'U')
                deq.push_front({pos.x, pos.y + 1});
            else if (C == 'D')
                deq.push_front({pos.x, pos.y - 1});

            deq.pop_back();
        }
        else if (x == 2)
        {
            int p;
            cin >> p;

            Position pos = deq[p - 1];

            cout << pos.x << " " << pos.y << endl;
        }
    }
}

atcoder.jp

実装時間: 25分