aoj2441:FizzBuzz
解法
あるxまでFizzBuzzしたときの文字列の長さを求めるのは、そんなに難しくない。
よって、FizzBuzzの文字列の長さがS未満であるようなxの中で最大のものを二分探索で求めて、
あとはそこから実際にFizzBuzzをして出力すればいい。
コード
#include<bits/stdc++.h> using namespace std; #define int long long typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define all(v) (v).begin(),(v).end() #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define pb push_back #define fi first #define se second template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} const int INF=1000000000000000000ll; int C(int x){ int d=1; int sum=0; for(int i=1;;i++){ int dd=d*10; int l=d-1,u=min(dd-1,x); int tmp=u/3-l/3; sum+=tmp*4; tmp=u/5-l/5; sum+=tmp*4; if(sum>=INF)return INF; tmp=u-l-(u/3-l/3)-(u/5-l/5)+(u/15-l/15); sum+=tmp*i; if(sum>=INF)return INF; d*=10; if(x<d)return sum; } } signed main(){ int S; cin>>S; int lb=0,ub=INF; while(ub-lb>1){ int mid=(ub+lb)/2; if(C(mid)<S)lb=mid; else ub=mid; } string str; for(int i=lb+1;i<lb+100;i++){ if(i%3==0&&i%5==0){ str+="FizzBuzz"; } else if(i%3==0){ str+="Fizz"; } else if(i%5==0){ str+="Buzz"; } else{ stringstream ss; ss<<i; str+=ss.str(); } } cout<<str.substr(S-C(lb)-1,20)<<endl; return 0; }