結果

問題 No.3136 F,B in FizzBuzzString16
ユーザー GOTKAKO
提出日時 2025-05-02 23:46:00
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,210 bytes
コンパイル時間 2,229 ms
コンパイル使用メモリ 209,660 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-05-02 23:46:04
合計ジャッジ時間 3,411 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 7
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto string16 = [&](long long x) -> string {
        if(x%15 == 0) return "FizzBuzz";
        else if(x%3 == 0) return "Fizz";
        else if(x%5 == 0) return "Buzz";

        string ret = "";
        while(x){
            long long r = x%16; x /= 16;
            if(r < 10) ret += '0'+r;
            else ret += 'A'+r-10;
        }
        reverse(ret.begin(),ret.end());
        return ret;
    };
    auto findC = [&](long long L,long long R) -> tuple<long long,long long,long long> {
        long long ret3 = R/3-(L-1)/3,ret5 = R/5-(L-1)/5,ret15 = R/15-(L-1)/15;
        return {ret3-ret15,ret5-ret15,ret15};
    };
    auto findR = [&](long long x) -> pair<long long,long long> {
        long long p16 = 1,d = 1;
        while(true){
            auto [f,b,fb] = findC(p16,p16*16-1);
            x -= p16*15*d;
            x += (f+b+fb)*d;
            x -= f*4+b*4+fb*8;
            if(x < 0){
                x += f*4+b*4+fb*8;
                x -= (f+b+fb)*d;
                x += p16*15*d;
                
                long long low = p16-1,high = p16*16;
                while(high-low > 1){
                    long long mid = (high+low)/2;
                    tie(f,b,fb) = findC(p16,mid);
                    long long X = x;
                    X -= (mid-p16+1)*d;
                    X += (f+b+fb)*d;
                    X -= f*4+b*4+fb*8;
                    if(X < 0) high = mid;
                    else low = mid;
                }
                tie(f,b,fb) = findC(p16,low);
                x -= (low-p16+1)*d;
                x += (f+b+fb)*d;
                x -= f*4+b*4+fb*8;
                return {low,x};
            }
            p16 *= 16,d++;
        }
    };

    vector<long long> P16(100,1);
    for(int i=1; i<100; i++) P16.at(i) = P16.at(i-1)*16;

    vector<vector<tuple<long long,long long>>> memo(100,vector<tuple<long long,long long>>(16,{-1,-1}));
    auto count = [&](auto count,long long d,long long r) -> tuple<long long,long long> {
        if(d < 0) return {0,0};
        if(get<0>(memo.at(d).at(r)) != -1) return memo.at(d).at(r);
        if(d == 0){
            if(r%15 == 0) return {2,1};
            if(r%3 == 0 || r%5 == 0) return {1,1};
            return {0,0};
        }
        long long ret = 0,ret2 = 0,memor = r;
        for(int i=0; i<16; i++){
            auto [add,minus] = count(count,d-1,r);
            ret += add; ret2 += minus;
            if(i == 11 || i == 15) ret += P16.at(d-1)-minus;
            r = (r+1)%15;
        }
        memo.at(d).at(memor) = {ret,ret2};
        return {ret,ret2};
    };
    auto solve = [&](long long x) -> long long {
        if(x == 0) return 0;
        auto [R,more] = findR(x);
        long long ret = 0;
        
        long long p16 = 1,d = 0; x = R;
        while(R >= p16*16){
            p16 *= 16; d++;
            auto [add,minus] = count(count,d,1);
            ret = add;
        }
        long long start = p16; 
        while(d >= 0){
            for(int i=0; i<16; i++){
                if(start+p16-1 > R) break;
                string s = string16(start);
                if(s.back() == 'z'){
                    s = string16(start+1);
                    if(s.back() == 'z') s = string16(start+2);
                    s.back() = '0';
                }
                long long one = 0;
                for(auto c : s) one += (c=='F')|(c=='B');
                if(p16 > 1){
                    auto [add,minus] = count(count,d,start%15);
                    ret += add;
                    ret += (p16-minus)*one;
                }
                else{
                    s = string16(start);
                    one = 0;
                    for(auto c : s) one += (c=='F')|(c=='B');
                    ret += one;
                }
                start += p16;
            }
            p16 /= 16,d--;
        }
        {
            string last = string16(R+1);
            for(int i=0; i<more; i++) ret += (last.at(i)=='F')|(last.at(i)=='B');
        }
        return ret;
    };

    long long X,Y; cin >> X >> Y;
    cout << solve(Y)-solve(X-1) << endl;
}
0