きままにものづくり

日々の気付いたことなんかを書いてます。

SRM633Div1Easy

問題

無限の平面とサイズNの数列が与えられる。数列の要素の値の距離だけジャンプができ、これを数列の順番通りに繰り返す。
(0, 0)から(0, x)へ移動するための最小のステップ数を求めよ。

解法

距離を半径とする円を考える。ジャンプを繰り返すことで円の幅を広げていく。初めは最小値 $a=0$ 、最大値 $b=0$ 、数列の要素の値を $r_i$ とする。最大値は $b += r_i$ で更新されていく。最小値の更新は以下となる。

$r \leq a:a - r$
$r \leq b: 0$
$b < r: r - b$

計算量

O(N)

コード