読者です 読者をやめる 読者になる 読者になる

AtCoder ABC056 C - Go Home

問題

時刻0に直線上の0地点にカンガルーがいる。時刻i - 1から時刻iにかけてカンガルーは現在地点pとするとp - i, p, p + 1のどれかに移動することができる。カンガルーが位置Xに到達する最短時間を求める問題。

C: Go Home - AtCoder Beginner Contest 056 | AtCoder

解法

X = 12に場合を考える。毎時刻、右に進むとき以下のようになる。(p = 位置(t = 時間)と表す)

0(0) →1(1) →3(2) →6(3) →10(4) →15(5)

この時、時刻t = 5の時の現在地はp = 15となりXとの差は3である。上の進み方の内、時刻2から3に変わる時に「動かない」という選択をすると最終地点は3だけマイナスとなりt = 5の時p = 12となりXに到達することができる。これは動きをしていないので最短時間での到達となる。

上記の移動方法をまとめると以下のようになる。

0(0) → 1(1) →3(2) → 3(3)→ 7(4) → 12(5)

全ての時刻で右に進んでいくと、p(position)がXを超えるときが来る。この位置の差をdiff = p - X (p >= X)と置くと、diffはこれまでのどこかの時刻で「動かない」という選択をすればpをXと一致させることができる。これは移動の仕方が、+1, +2, +3, ,,,, + tとなっているからである。

まとめると、時刻tまで全て右に進んだ時の位置はp = (1 + 2 + 3 +, ... + t)となり、(p >= X)となる最小のtが答えとなる。

等差数列の和の公式

今回の移動方法は、全て右に進んだ場合{1, 2, 3, 4, 5, 6, …., t}となる。これは等差数列であり、この数列の項の総和は等差数列の和の公式によってO(1)で求めることができる。

等差数列の和の公式
sum = (項の数 * (初項 + 末項) / 2) = (t * (t + 1)) / 2

ソースコード