大変そう・・・。問題を分割すると、
- ある数字までのFizzBuzz String の長さを高速に計算する
- ↑の数字を[0, s)の間で二分探索
というところまで分かる。
なぜ二分探索が出てくるかというと、
ある数字までのFizzBuzz Stringの長さは単調増加しているから。
FizzBuzz Stringの長さがs以下となる最大の「ある数字」を求めるということ。
ある数字までのFizzBuzz Stringの長さは、ある数字をnとしたとき
O(log n)で求めることができる。
各桁数ごとに、(9999 - 999) * 4というように数えていき、
3の倍数、5の倍数の数だけ引き、15の倍数の数を足し、
3の倍数、5の倍数の数だけ4(len("Fizz"), len("Buzz"))を足す。
終端も同様に行う
(ごちゃごちゃしていますが、関数funcにまとめています)。
これでO(log^2 s)
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2353262#1
1-indexedに少し苦労した。
時間を計ったら1:04:28.42と出た。
こんなものかなあ(もう少し早く解きたい)。