Hatena::Grouptopcoder

not's memo

2015-08-06

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

23:48 | はてなブックマーク - yukicoder No.262 面白くないビットすごろく - not's memo

出題しようと準備していた問題が想定TLE解法で出題されてしまって、とても悲しい気分になったので解説を書きました。。。


用意していた問題

Xから立ってるビットの数だけ足すというのをK回くりかえすと何になるか?

X,KはT個与えられる。

X,K<10^17, T<10^5


解法

[7ビット目以降でいくつビットが立っているか][7ビット目以降でいくつ立っていないビットが続くか][下6ビット]を状態とする。

それぞれの状態について7ビット目以降で初めて立っているビットが0になるまで足すのに何回かかるか・0になった時の下6ビットを計算する。

これは各状態についてO(1)でできる。


次にXの7ビット目以降で初めて立っているビットが0になるまで足す。

これは前計算の結果を用いればO(1)。

これを足し算がK回以下になるように繰り返す。


足し算がK回以下に収まらなくなったら今度は逆に見るビットを1つずつ下げながら足していく。

これも各ビットについてO(1)。

前の操作と違って、ビットが立っていなくても足すことに注意。


最後に、残った回数だけ愚直に足す。


計算量はO(log^3 (X + K) + T log (X + K))くらい。