公式
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)\) です。
投稿日時:
最終更新: