概要

座標 \(0\) から始めて、右または左への移動を順番に処理し、各移動直後の座標を出力する問題です。右に進んだ距離の合計と、左に進んだ距離の合計を管理します。

考察

数直線上では、右への移動は座標を増やし、左への移動は座標を減らします。そのため、現在の座標は次の式で求められます。

\(\text{現在の座標} = \text{右に進んだ距離の合計} - \text{左に進んだ距離の合計}\)

例えば、R 5、L 3、L 4 の順に移動すると、次のようになります。

この問題は、移動をそのまま順番に処理する素朴なシミュレーションで十分に間に合います。距離 \(1\) ずつ移動を再現する必要はなく、移動距離をまとめて加算すれば、各移動を定数時間で処理できます。

なお、求められるのは原点からの距離ではなく、符号付きの座標です。左への移動が多ければ座標は負になるため、差の絶対値を取ると誤答になります。

アルゴリズム

1. 移動回数 \(N\) を読み込みます。
2. 右への移動距離の合計 right と、左への移動距離の合計 left を、ともに \(0\) で初期化します。
3. 各移動について、次の処理を行います。
   • 方向 \(D_i\) と距離 \(X_i\) を読み込みます。
   • \(D_i\) が R なら、right に \(X_i\) を加えます。
   • \(D_i\) が L なら、left に \(X_i\) を加えます。
   • right - left を出力します。

各移動の処理後、right と left はそれぞれ、その時点までに右・左へ進んだ距離の合計です。初期座標は \(0\) なので、その差を出力すれば、移動直後の正しい座標が得られます。

計算量

• 時間計算量: \(O(N)\)
  各移動を定数時間で処理します。
• 空間計算量: \(O(1)\)
  移動の履歴を保存せず、合計値などの変数だけを使用します。

実装のポイント

• 合計値を更新した後に出力します。更新前に出力すると、移動直後の座標になりません。

• 初期座標 \(0\) は出力せず、各移動後の座標を合計 \(N\) 行出力します。

• 制約より座標の絶対値は最大 \(100 \times 1000 = 100000\) なので、C++ の int でも扱えます。提示コードでは long long を使用しています。

• 方向は L または R のみなので、d == 'R' でなければ左への移動として処理できます。

  ソースコード

// 問題文から独立に実装: 右への合計と左への合計を別々に持つ
#include <iostream>
int main() {
    int n; std::cin >> n;
    long long right = 0, left = 0;
    while (n--) {
        char d; long long x; std::cin >> d >> x;
        if (d == 'R') right += x; else left += x;
        std::cout << right - left << "\n";
    }
}

この解説は gpt-6-astra-medium によって生成されました。