mayoko’s diary

プロコンとかいろいろ。

AOJ 2441: FizzBuzz

解法

二分探索します。

calc(x) = ([1, x] まで fizzbuzz を書いた時の文字数), とすると, これは [1, 10), [10, 100), ..., [10^(n-1), 10^n) , [10^n, x] の文字数をそれぞれ調べれば求めることが出来ます。

これで calc(x) < s を満たす最大の x が分かれば, あとは x+1 から順番に出来る文字列を試して, 20 文字になるまで足していけば良いです。

// [l, r)
ll countNum(ll l, ll r, ll div) {
    return (r-1)/div - (l-1)/div;
}

// x まで書くと何文字書くことになるかを求める
ll calc(ll x) {
    ll p = 1;
    ll ans = 0;
    int cnt = 1;
    while (10*p < x) {
        ll np = p*10;
        // [p, np) で何文字になるか
        ll fizzbuzz = countNum(p, np, 15);
        ll fizz = countNum(p, np, 3) - fizzbuzz;
        ll buzz = countNum(p, np, 5) - fizzbuzz;
        ll other = (np-p) - (fizz+buzz+fizzbuzz);
        ans += fizzbuzz*8 + fizz*4 + buzz*4 + other*cnt;
        cnt++;
        p = np;
    }
    // [p, x] における文字数
    ll fizzbuzz = countNum(p, x+1, 15);
    ll fizz = countNum(p, x+1, 3) - fizzbuzz;
    ll buzz = countNum(p, x+1, 5) - fizzbuzz;
    ll other = (x+1-p) - (fizz+buzz+fizzbuzz);
    ans += fizzbuzz*8 + fizz*4 + buzz*4 + other*cnt;
    return ans;
}

const string number = "0123456789";

string trans(ll x) {
    if (x%15==0) return "FizzBuzz";
    if (x%5==0) return "Buzz";
    if (x%3==0) return "Fizz";
    string ret;
    while (x) {
        ret += number[(int)(x%10)];
        x /= 10;
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

int main() {
    ll s;
    cin >> s;
    ll low = 0, high = 1ll<<58;
    // calc(x) < s を満たす最大の x を求める
    while (high-low > 1) {
        const ll med = (low+high)/2;
        if (calc(med) >= s) high = med;
        else low = med;
    }
    s -= calc(low)+1;
    // こっからは愚直にやってく
    string ans;
    while (1) {
        string t = trans(++low);
        if (s > 0) {
            ans += t.substr((int)s);
            s = 0;
        } else {
            int i = 0;
            while (ans.size() < 20 && i < (int)t.size()) ans += t[i++];
        }
        if (ans.size()==20) break;
    }
    cout << ans << endl;
    return 0;
}