Posted at

ABC056 C問題の解説の補足

https://atcoder.jp/contests/abc056/tasks/arc070_a

C問題の解説を読んだり、他の人の解答を読んでも何故そうなるのかがわからなかったが、最終的に証明っぽいことができたので復習のために記録。

解答例としては与えられた X 以上となるまで初期値1,等差数列1の数列の和を算出し続けていく、和がX以上になった時、それまでの数列の数が解答となる。

https://atcoder.jp/contests/abc056/submissions/6222759


証明

等差数列の和がX超えた時の等差数列の和をSum、最後に足した数値をNSumのために足した数列数値の数をTとする。

ここでSum > Xである。

また、Sum - X < Nである。

(もしSum - X = Nなら、解答は`T-1`となるためである)

ここで、Sumはカンガルーが毎秒右にジャンプした時に到達する距離を表している。

Sum - N < Nなので、1 ~ N-1の中でSum - Nの手番にその場にとどまることによって手番 N での到達距離を X 丁度にできる。