Aizu Online Judge 2441 - FizzBuzz

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2441

解法

問題文の制約により、十分に長いFizzBuzz文字列を作ってから20文字を調べるという手法はとれません。そこで別の解法を探します。
ここである整数が与えられた時、FizzBuzz文字列の先頭から何番目におけばいいということは、3の倍数、5の倍数, 15の倍数を数えることにより高速に求めることができます。ただ桁数がFizzBuzz文字列の長さに影響するので、桁数で場合分けしなければならないことに注意します。
あとは開始位置がを満たすような最大の整数を見つけることにより、必要な部分のFizzBuzz文字列の復元ができます。そのようなは二分探索により高速に求めることができます。

ソースコード

#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

ll s;

/*
 * FizzBuzz文字列におけるxの開始位置(0-indexed)を返す. 
 * sを超えることがわかったら-1を返す.
 */
ll Index(ll x) {
    ll num = 1,             // 現在調べている桁の最初の数
       fizzbuzz_len = 0;    // num-1までのFizzBuzz文字列の長さ
    int digits_num = 1;     // 現在調べている桁数
    while (num < x && fizzbuzz_len <= s) {
        ll mul_15_num = (min(num * 10, x) - 1) / 15 - (num - 1) / 15,
           mul_3_num  = (min(num * 10, x) - 1) / 3 - (num - 1) / 3,
           mul_5_num = (min(num * 10, x) - 1) / 5 - (num - 1) / 5,
           other_num = min(num * 10, x) - num - (mul_3_num + mul_5_num - mul_15_num);

        fizzbuzz_len += mul_15_num * 8;
        fizzbuzz_len += (mul_3_num - mul_15_num) * 4;
        fizzbuzz_len += (mul_5_num - mul_15_num) * 4;
        fizzbuzz_len += other_num * digits_num;

        num *= 10;
        digits_num++;
    }
    return fizzbuzz_len <= s ? fizzbuzz_len : -1;
}

int main() {
    cin >> s;
    s--;        // 0-indexedにするため
    ll lb = 0, ub = (1LL << 60);

    while (ub - lb > 1) {
        ll mid = (ub + lb) / 2, index = Index(mid);
        if (index >= 0) {
            lb = mid;
        } else {
            ub = mid;
        }
    }
    ll index = Index(lb);

    string fizzbuzz = "";
    ll num = lb;
    while (fizzbuzz.size() < s - index + 20) {
        if (num % 15 == 0) fizzbuzz += "FizzBuzz";
        else if (num % 3 == 0) fizzbuzz += "Fizz";
        else if (num % 5 == 0) fizzbuzz += "Buzz";
        else fizzbuzz += to_string(num);
        num++;
    }

    cout << fizzbuzz.substr(s - index, 20) << endl;

    return 0;
}

感想

昔解いた問題ですが、勉強会で出されていたので解き直しました。