概要
問題文 → ■
公式解説 → ■
自分の提出 → ■
埋め込みとか、 単位の計算量を仮定した解説しかなかったので、一応書きます。
たとえば制約が、 でもすぐに答が出ます。
解法
次の計算を行う関数を考えます。
:「 に居るときに、 だけ進む」という新しいゲームを考える。 から始めて、 になるまで進むときの、手数と終着地点をかえす。
たとえば、 を計算すると、 → → → → より、 が返るという要領です。
が小さな場合は愚直に計算して、 が大きな場合には次の要領で再帰的に計算できます。
たとえば、 を計算したいとします。 以上になるまでの計算を返すことが目標です。まず、 を超えるまでの計算をします。 が小さな場合が計算されているとすると、 より 歩で に到達することが分かります。
そこから に到達するまでの過程は、最上位の「1」のおかげで、下 桁だけ見たときのゲームよりも だけ余分に進みながら行うことと等価です。 を元に、 から 手先に、 に到達できることが分かります。
さて、 がすべて計算できると、元の問題( 以上に到達するまでシミュレート)も簡単です。距離が より大きいうちは、 として、 により次の の倍数以上になるまで進む計算を行えます。
計算量は、厳密なことは検討していませんが、 かつ に対する を全部計算してしまうことが、1 件あたり で行えます。したがって、 で解くことが可能です。
全部の を計算する必要はないような気がしますが…結局定数倍くらいで になるかもしれません。私はメモ化再帰の形で実装しました。