[yukicoder] No.262 面白くないビットすごろく

スポンサーリンク

概要

問題文 →
公式解説 →
自分の提出 →

埋め込みとか、N 単位の計算量を仮定した解説しかなかったので、一応書きます。
たとえば制約が、N1018 でもすぐに答が出ます。

解法

次の計算を行う関数を考えます。

f(a,b,c):「n に居るときに、popcount(n)+a だけ進む」という新しいゲームを考える。n=b から始めて、n2c になるまで進むときの、手数と終着地点をかえす。

たとえば、f(2,1,4) を計算すると、1471216 より、(4,16) が返るという要領です。

c が小さな場合は愚直に計算して、c が大きな場合には次の要領で再帰的に計算できます。

たとえば、f(0,1,10) を計算したいとします。210=1024 以上になるまでの計算を返すことが目標です。まず、29 を超えるまでの計算をします。c が小さな場合が計算されているとすると、 f(0,1,9)=(125,515) より 126 歩で n=515 に到達することが分かります。

そこから 1024 に到達するまでの過程は、最上位の「1」のおかげで、下 9 桁だけ見たときのゲームよりも 1 だけ余分に進みながら行うことと等価です。f(1,3,9)=(98,519) を元に、n=515 から 98 手先に、n=512+519=1031 に到達できることが分かります。

さて、f(a,b,c) がすべて計算できると、元の問題(N 以上に到達するまでシミュレート)も簡単です。距離が 2c より大きいうちは、n=2cq+r として、f(popcount(q),r,c) により次の 2c の倍数以上になるまで進む計算を行えます。

計算量は、厳密なことは検討していませんが、b,c<lgN かつ a<lgNc に対する f(a,b,c) を全部計算してしまうことが、1 件あたり Θ(1) で行えます。したがって、O(lgN3) で解くことが可能です。

全部の (a,b,c) を計算する必要はないような気がしますが…結局定数倍くらいで Ω(lgN3) になるかもしれません。私はメモ化再帰の形で実装しました。

タイトルとURLをコピーしました