C - Loong Tracking / AtCoder Beginner Contest 335（Sponsored by Mynavi）

問題

座標平面上に龍がおり、龍は から までの番号がついた 個のパーツから構成される。 また、パーツ を頭と呼ぶ。

最初、パーツ は座標 にあるとき、以下のクエリを 個処理せよ。

• 1 c: 頭を方向 に だけ移動させる。
  • は R, L, U, D のいずれかであり、それぞれ 軸の正方向、 軸の負方向、 軸の正方向、 軸の負方向を表す。
  • 頭以外のすべてのパーツは、前のパーツに追従するように動く。
    • すなわち、パーツ は、移動前にパーツ があった座標に移動する。
• 2 p : パーツ のある座標を求める。

入力

まず最初の1行目に、整数 が与えられる。

次の 行では、クエリが1行ごとに与えられる。 クエリは 1 c の形式か 2 p の形式で与えられる。

条件

• 
• 
• は R, L, U, D のいずれかである。
• 

出力

2種類目のクエリの解答について、答えとなる座標 を1行ずつ出力すること。

解法

まずは「移動が発生するたびに、すべてのパーツの座標を更新する」という方法が思いつきます。 しかし、1回の移動につき 個のパーツが動くことから、最大で の計算量がかかってしまい、これでは実行時間制限には間に合いません。

そこで、「頭以外のパーツは、前のパーツがあった位置に移動する」ということに着目します。

ここで、 回目の移動が起こった直後に頭のパーツがある位置座標を として定義します。 なお、頭のパーツの初期座標は とし、 個目のパーツの初期座標を と表します。

このとき、移動が起こるたびに、各パーツの座標は以下の図のように変遷していきます。

図から、 回目の移動が起こった直後での、 個目のパーツの座標は であるということが言えます。

従って、移動が起こるたびに頭のパーツの座標をC++での std::vector などを使用して保存していくことで、 個目のパーツの座標を で取り出すことができます。

以上から、この問題を解くには、

1. を保存しておく
2. 回目の移動が発生したら、 の値から を計算し、保存する
3. 回の移動が発生している状態で 個目のパーツの座標を聞かれたら、 の値を出力する

という手順を踏めばいいということがいえます。 この手順では、 の計算量が必要になりますが、これは実行時間制限には十分間に合います。

ソースコード

int n, q;
vector<Pii> pos; // 位置座標を保存するための pair<int, int> の vector

const char dir[4] = {'R', 'L', 'U', 'D'}; // 与えられる方向の文字
const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1}; // dx, dy はそれぞれ dir に対応する x, y の方向を表す

int main() {
  // 値の入力
  cin >> n >> q;

  // パーツ n から順に、初期位置の座標を pos に保存する
  for (int i = n; i >= 1; i--) {
    pos.push_back({i, 0});
  }

  // クエリの処理を行う
  for (int i = 0; i < q; i++) {
    int num; // クエリの種類を表す番号
    cin >> num;

    if (num == 1) {
      // クエリ1の場合
      // 方向を表す文字を入力する
      char c;
      cin >> c;

      // pos の最後尾の値が現在の頭のパーツの位置なので、それを t として宣言する
      Pii t = pos[pos.size() - 1];

      // c と一致する dir[k] の値を探し、一致したら pos に追加する
      for (int k = 0; k < 4; k++) {
        if (c == dir[k]) {
          pos.push_back({t.first + dx[k], t.second + dy[k]});
        }
      }
    } else {
      // クエリ2の場合
      // 座標を求めるパーツの番号を入力する
      int p;
      cin >> p;

      // 最後尾から p 番目の座標が出力すべき座標なので、それを出力する
      cout << pos[pos.size() - p].first << " " << pos[pos.size() - p].second << endl;
    }
  }

  return 0;
}

• 提出したコード: https://atcoder.jp/contests/abc335/submissions/49349059
• GitHub

感想

C++ での std::vector の .push_back() が末尾に値を追加するものなので、インデックスの管理について考える必要がある問題でした。