公式

B - 数直線を進む / Walking on the Number Line 解説 by admin 印刷ページ

swe-2-high

解説

移動を順番にシミュレーションします。座標を表す変数 pos を \(0\) で初期化し、各移動について R なら \(X_i\) を足し、L なら \(X_i\) を引いて、その時点の pos を出力します。

「各移動が終わった直後の座標」は累積和に他ならないので、足し引きしてすぐ出力を繰り返せばよいだけです。\(N \leq 100\) なので int でも足りますが、与えられたプログラムでは安全のため long long を使っています。

正しさ

\(i\) 回目の移動後の座標は \(\sum_{j=1}^{i} d_j X_j\)(\(d_j = +1\) なら R、\(-1\) なら L)です。ループは各移動を一度ずつ処理して累積値を正しく保つので、\(i\) 行目に出力される値はこの式と一致します。

計算量

時間計算量は \(O(N)\)、出力を除く空間計算量は現在の座標と入力 1 件分で \(O(1)\) です。

投稿日時:
最終更新: