GCJ 1B: A. Counter Culture

問題

自然数xに対して
・1増やす
・10進表示を逆順にする
という操作を任意に行うことが出来る。
1からスタートして入力nまでたどり着くまでに最小で何ステップ必要か。

解法

nが1桁だったらそのままnを出力すれば良い。
逆順にしても桁数が減るわけではないので一桁ずつ減らして行くことを目標に考える。
つまり入力nがm桁だとすると、n を 10^(m-1) -1 に持って行くまでに最小で何ステップ必要かを考える。そのためにはデクリメントを出来るだけ少ない回数適用すれば良いが、色々考えてみるとnの10 進表示を2等分して、後ろの方を00…01の形にした後にreverseして前者を00…1にすれば最終的にnは100…001の形になって2回デクリメントすて1桁減らすことが出来る。
つまり、nを二等分して前半をreverseして得られる数字、後半の数字をそれぞれ求めてそれらを00…01にするまでに必要なステップ数(求めた数字-1) + 1(reverseの分) + 2(99..99にするのに必要な分)
を求めた後に99…99をまた再帰的に求めれば良い。
しかしnが例えばn=100321とかだとreverseの分を足す必要はないので注意。

(こんな感じ)