8時開始なら8時開始って言ってよねもぉ~(大遅刻)(※言われてました)
桁DPっぽいけど、なんか上手く当てはめきれなくて手間取った。
「10進数表記にしたときの桁数」と「何桁目か」ごとに、答えへの寄与を求める。
N = 1113012 7桁 1桁目 1xxxxxx ... 1000000 ~ 1113012 の (1113012 - 1000000 + 1) 個 7桁 2桁目 11xxxxx ... 1100000 ~ 1113012 の (1113012 - 1100000 + 1) 個 7桁 3桁目 111xxxx ... 1110000 ~ 1113012 の (1113012 - 1110000 + 1) 個 7桁 4桁目 1111xxx ... 1111000 ~ 1111999 の (1112000 - 1111000) 個 7桁 5桁目 11111xx ... 1111100 ~ 1111199 の (1111200 - 1111100) 個 ... 6桁 1桁目 1xxxxx ... 100000 ~ 199999 の ( 200000 - 100000) 個 6桁 2桁目 11xxxx ... 110000 ~ 119999 の ( 120000 - 110000) 個 ... ※xで表された箇所は、Nを超えない限り何でもよい
このように、$k$ 桁目を考えるときは先頭 $k$ 個を $1$、残りを $0$ にした数を $X$ とし、
「$N+1$」と「$X$ の最後の $1$ を $2$ にしたやつ」の小さい方から $X$ を引いた個数だけ、答えに寄与する。
ただし、$N=11103$ のように $1$ が連続した次に $0$ が来るケースは、 4桁目の $X=11110$ を考慮する際に個数が負になってしまうので、$N \lt X$ となったらその桁数はそこで打ちきる。
$X$ 番目を高速に見つける方法を発見するのが1点、2進数で与えられる $X$ を上手く処理するのが1点。
とりあえず実験してみると、先頭は'1'なのは全て共通として、後は自己相似形っぽくなっている。
N=4 桁は下から数えるとして、 1--- 3桁目に着目すると、'-' が1つ、'0' が7つ、'1' が7つ 10-- | 100- |-- 3桁目が'0'である7つの 2桁目に着目すると 1000 | '-' が1つ、'0' が3つ、'1' が3つ 1001 | (これは3桁目が'1'の7つでも同じ) 101- | | 1010 | |-3桁目が'0'、2桁目が'1'の3つの1桁目に着目すると、 1011 | | '-' が1つ、'0' が1つ、'1' が1つ 11-- (これは3桁目、2桁目が同じ他のグループでも同じ) 110- 1100 1101 111- 1110 1111
従って、以下のようにすると答えが求められる。
ans = 1
とする(文字列として扱う)ans
が答えans
末尾に '0' を加え、$X←X-1$ とするans
末尾に '1' を加え、$X←X-2^{d-1}$ とするよっしゃ、Pythonなら多倍長も扱えるしこれをそのまま実装すれば勝ったな。ガハハ。
だが、いくら多倍長が扱えるといってもさすがに $2^{1000000}$ に近い数を $10^6$ 回演算するのはTLEとなる(なった)。
$X$ が2進数で与えられること、また各桁で'0'と'1'のどちらを追加するかは $2^{d-1}$ 以下か超過かで判定できることから、
X = 1100110 N=9 ↓ X = [0, 0, 1, 1, 0, 0, 1, 0, 1]
とした上で、以下の3種類の演算を実装すればよい。
で、最後が1個ずつ見ていくので計算量的に不安になるが、実はこれは大丈夫。
1回、なかなか '1' が見つからないでたくさん遡った後は、下の桁は '1' で埋められる。
そしたらしばらくは、再びたくさん遡ることは無い。
A問題をひっくり返した感じで、 下から $k$ 桁目まで遡られる期待値を $k$ 毎に考えると、$2^{k-1}$ 回に1回なので、 $1+\dfrac{1}{2}+\dfrac{1}{4}+...=2$ に収束する。1回あたり均し $O(1)$ で済む。
(今回は1を引く演算しか無いのでこれが言えるが、足したり、他の演算も絡んでくる場合はそうとは限らないので注意)