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) →３(2) →６(3) →１０(4) →１５(5)
この時、時刻t = 5の時の現在地はp = 15となりXとの差は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)となる最小のｔが答えとなる。
等差数列の和の公式
今回の移動方法は、全て右に進んだ場合{1, 2, 3, 4, 5, 6, …., t}となる。これは等差数列であり、この数列の項の総和は等差数列の和の公式によってO(1)で求めることができる。
等差数列の和の公式
sum = (項の数 * (初項 + 末項) / 2) = (t * (t + 1)) / 2
