AOJ 2441 : FizzBuzz

FizzBuzz | Aizu Online Judge

大変そう・・・。問題を分割すると、

  • ある数字までのFizzBuzz String の長さを高速に計算する
  • ↑の数字を[0, s)の間で二分探索

というところまで分かる。
なぜ二分探索が出てくるかというと、
ある数字までのFizzBuzz Stringの長さは単調増加しているから。
FizzBuzz Stringの長さがs以下となる最大の「ある数字」を求めるということ。

ある数字までのFizzBuzz Stringの長さは、ある数字をnとしたとき
O(log n)で求めることができる。

f:id:arukuka:20170604175248p:plain

各桁数ごとに、(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と出た。
こんなものかなあ(もう少し早く解きたい)。