ARC127 A - Leading 1s (300)
コンテスト中の考察
$ dp[i][j][k][l] としてd桁目、1がj個頭から継続していてkで継続中か否か、lが$ Nと同じ値か未満かという桁DPをする
未満になっていない場合、
$ i桁目が1ならdp[i][j+1][1][0] += dp[i-1][j][1][0];, dp[i][j][0][1] += dp[i-1][j][0][0] + dp[i-1][j][1][0];
未満の場合に移行するのは0にした場合のみ
そうでないならdp[i][j][0][0] += dp[i-1][j][1][0] + dp[i-1][j][0][0];, REP(k,2,a[i]+1) dp[i][j][0][1] += dp[i-1][j][1][0] + dp[i-1][j][0][0];
$ i桁目が0より大きいなら0も使えるのでその分が含まれる
また1にすることもできるのでdp[i][j+1][1][1] += dp[i-1][j][1][0];
未満になっているなら好きに桁の値を設定できる
1にした場合、dp[i-1][j][1][1]をdp[i][j+1][1][1]に、dp[i-1][j][0][1];をdp[i][j][0][1]に足す
1でないなら、どちらも新しく1が伸びないのでdp[i][j][0][1]に足す
6WAで駄目
解説の解法
1が$ k個並んでいる場合について考える
最初の区間には$ 10^0個、次の区間は$ 10^1, \cdots, 10^x個という風に増えてゆく
これを$ nを越えないところまで調べれば良い
1が連続する数は$ \mathcal{O}(\log N)で$ nを越えるまで調査する数も$ \mathcal{O}(\log N)なので全体で$ \mathcal{O}(\log^2 N)