問題概要

FizzBuzzで出力する文字を連結したもの (この問題ではFizzBuzz Stringと呼ぶ) のうち，$ s ( s \leq 10^{18} ) $ 文字目から20文字分を出力する．

解法概要

1からnまでの分のFizzBuzzを出力したときのFizzBuzz Stringの文字数を求めることができれば，出力を決めるときにどこからFizzBuzzをすれば良いか2分探索で求めることができる．

肝心のFizzBuzz Stringの文字数の求め方を考える．1からnまでのFizzBuzz Stringの文字数をfizzbuzz_string(n)，1からnまでのdの倍数の文字数の和をnum_string(n, d)とすると，

fizzbuzz_string(n) = num_string(n, 1) - num_string(n, 3) - num_string(n, 5) + num_string(n, 15) + (3の倍数の個数)×4 + (5の倍数の個数)×4

num_string(n, 1)というのは要は1からnまでの数字の文字数のことで，ここから一度3の倍数と5の倍数の分の文字数を引いておく．ただし，それでは15の倍数の分が2回引かれてしまうので，15の倍数の分の文字数を足しておく．これにFizzの分とBuzzの分の字数を足せばFizzBuzz Stringの文字数がわかる．

num_string(n,d)は桁数ごとにdの倍数の個数を考えて足していくと簡単．nは最大10¹⁸なので18桁の数まで考えておけば確実に足りるはず (ソースコードでは10¹⁸ちょうどの分まで考えてある) ．

2分探索で出力文字列における開始時のFizzBuzzの値を求めたら，FizzやBuzz，数字列の途中から出力から出力するということもありうるので，出力をぴったりs文字目からにするためのズレを計算しておく．そのズレを考慮して20文字出力すればOK．

ソースコード

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

typedef unsigned long long ll;

ll num_string(ll n, ll d) {
    ll ret = 0, pow10 = 1, total = 0;
    for(int i=0;i<18;i++) {
        if(n >= pow10) {
            ll upper_lim = min(n, pow10*10-1);
            ret += (upper_lim/d - total) * (i+1);
            total = upper_lim/d;
        }
        pow10 *= 10;
    }
    if(n == pow10) ret += 19;
    return ret;
}

ll fizzbuzz_string(ll n) {
    ll ret = num_string(n, 1) - num_string(n, 3) - num_string(n, 5) + num_string(n, 15);
    ret += 4 * (n/3) + 4 * (n/5);
    return ret;
}

string output(ll n, ll rest) {
    string ret = "";
    int count = 0;
    while(count < 20+rest) {
        n++;
        bool isnum = true;
        if(n % 3 == 0) {
            ret += "Fizz";
            count += 4;
            isnum = false;
        }
        if(n % 5 == 0) {
            ret += "Buzz";
            count += 4;
            isnum = false;
        }
        if(isnum) {
            string n_str = to_string(n);
            ret += n_str;
            count += n_str.length();
        }
    }
    return ret.substr(rest, 20);
}

string solve(ll s) {
    ll ok = 0, ng = 1e18;
    while(ng-ok > 1) {
        ll mid = (ok+ng)/2;
        if(fizzbuzz_string(mid) < s) {
            ok = mid;
        }else{
            ng = mid;
        }
    }

    ll rest = s - 1 - fizzbuzz_string(ok);
    return output(ok, rest);
}

int main() {
    ll s;
    cin >> s;
    cout << solve(s) << endl;
}

所感

これすき．AOJ-ICPCで☆つけさせていただきました．

1からnまでの数字の文字数を考える時に桁ごとに数えて足していくのはおそらく典型なのではないかと思う．勉強になった．

NoiminのNoise

JAG夏合宿2012 Day3B B - FizzBuzz

問題概要

解法概要

ソースコード

所感