ABC029 D. 1

その他

問題

1からNまでの数字をすべて書き出したとき、「1」は何回書いたか？


1<=N<10^9

考え方

愚直に数えると、O(N*桁数)かかってしまって間に合わない。
以下、1からではなく、0から考えても問題ない。

桁DP

最大桁から考える。
ここで、Nが3桁「xyz」であると仮定する。
100の位は0〜xまであり得るが、0〜x-1までは、10の位以下は00〜99までの1の出現数、xの場合は00〜yzまでの出現数を使ってDPで求められる。

出現パターン

1の位は01234567890123456・・・を繰り返しており、10の位は00000000001111111111・・・・というパターンを繰り返している。
1の出る回数はそれぞれの桁でO(1)で求められるので、全体でO(桁数)しかかからない。