ARC123 A Arithmetic Sequence
操作後の$ A_1, A_2, A_3を$ A_1', A_2', A_3'とおく. すると, $ A_2' - A_1' = A_3' - A_2', すなわち$ 2A_2' = A_1' + A_3'となるような操作回数の最小値を求めればよいことになる. この問題は次のように場合分けすることにより解くことができる.
$ 2A_2 \geq A_1 + A_3のとき
$ A_1, A_3のどちらかを増やしていくのが最適であり, 答えは$ 2A_2 - A_1 - A_3となる.
$ 2A_2 < A_1 + A_3のとき
$ K = \lfloor \frac{A_1 + A_3 - 2A_2}{2} \rfloorとおく. ここで, $ A_1 + A_3が偶数の場合, $ A_2を$ K回増やすことにより条件を満たせるため, 答えは$ K回となる. $ A_1 + A_3が奇数の場合, $ A_2を$ K + 1回増やしたうえ, $ A_1,A_3のどちらかを$ 1回増やさなければならないため, 答えは$ K + 2回となる.
よってこの問題を適切な場合分けにより$ O(1)で解くことができた.