解法

高橋君の現在座標を position として管理し、最初は 0 にします。各移動を入力順に処理し、D_i が R なら X_i を加え、L なら X_i を引きます。各移動の直後に position をそのまま出力します。入力を配列に保存する必要はなく、各行を読みながら逐次処理できます。

正しさの証明

各反復の直前において、position がそれまでに完了した移動後の高橋君の座標に等しいという不変条件を考えます。

• 初期状態: 移動前の座標は 0 であり、position も 0 に初期化されているため成立します。
• 維持: i 回目の移動が R の場合、座標は正の方向に X_i だけ進むので、新しい座標は以前の座標に X_i を加えたものです。L の場合は負の方向に X_i だけ進むので、新しい座標は以前の座標から X_i を引いたものです。プログラムはまさにこの更新を行うため、反復後も不変条件が維持されます。

したがって、数学的帰納法により、各 i 回目の移動直後に出力される値は、その時点での正しい座標です。また、プログラムは各移動を入力順にちょうど一度ずつ処理するため、出力の個数と順序も正しいです。

計算量

• 時間計算量: O(N)
• 補助空間計算量: O(1)

入力は逐次読み込み、各出力行もその場で書き出すため、入力や出力全体を保持する配列は使用しません。順位付けや選択が存在しないため、特別なタイブレークはありません。