ferinの競プロ帳

競プロについてのメモ

AOJ2441 FizzBuzz

問題ページ
FizzBuzz | Aizu Online Judge

考えたこと

  • 数xまでの文字数が何文字になるか
  • Fizz,Buzzの部分は文字数が固定だからいいけど数字部分の文字数がずれるのがつらそう
  • ずれないように桁ごとに分ける
  • 1~9の中の3,5,15の倍数の数を数えると1~9のFizzBuzz stringの文字数がわかりそう
  • 他の桁数でも同様
  • したがって数xまでのFizzBuzz stringが何文字かはO(logx)で数えられる
  • こういう制約はどうせ周期性とかの規則があるか二分探索ができるかなので(は?)考えると二分探索ができそう
  • 数xまでの文字数がs以下か として二分探索をするとどの数からFizzBuzz stringをつくればいいのかがわかる
  • 頑張って実装すると通った

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

int len[30];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int s;
  cin >> s;

  int sum = 0;
  auto check = [&](int m) -> bool {
    sum = 0;
    int i, l;
    for(i=1, l=1; i<=m; i*=10, ++l) {
      // [i, 10*i)
      int a = (10*i-1)/3 - (i-1)/3;
      int b = (10*i-1)/5 - (i-1)/5;
      int c = (10*i-1)/15 - (i-1)/15;
      a -= c, b -= c;
      sum += (a + b + 2*c) * 4 + (10*i-i-a-b-c) * l;
    }
    // (m, i) を引く
    if(m < i) {
      int a = (i-1)/3 - m/3;
      int b = (i-1)/5 - m/5;
      int c = (i-1)/15 - m/15;
      a -= c, b -= c;
      sum -= (a + b + 2*c) * 4 + (i-1-m-a-b-c) * (l-1);
    }
    return sum < s;
  };

  int lb = 0, ub = 1e18;
  while(ub-lb>1) {
    int mid = (lb+ub)/2;
    if(check(mid)) {
      lb = mid;
    } else {
      ub = mid;
    }
  }
  // lb+1 の s - sum番目からのFizzBuzz string
  check(lb);

  int idx = lb+1;
  string ans = "";
  if(idx%15 == 0) {
    string tmp = "FizzBuzz";
    ans += tmp.substr(s-sum-1);
  } else if(idx%3==0) {
    string tmp = "Fizz";
    ans += tmp.substr(s-sum-1);
  } else if(idx%5==0) {
    string tmp = "Buzz";
    ans += tmp.substr(s-sum-1);
  } else {
    string tmp = to_string(idx);
    ans += tmp.substr(s-sum-1);
  }
  idx++;
  while(ans.size() < 20) {
    if(idx%15 == 0) {
      string tmp = "FizzBuzz";
      if(ans.size() + 8 <= 20) {
        ans += tmp;
      } else {
        ans += tmp.substr(0, 20-ans.size());
      }
    } else if(idx%3==0) {
      string tmp = "Fizz";
      if(ans.size() + 4 <= 20) {
        ans += tmp;
      } else {
        ans += tmp.substr(0, 20-ans.size());
      }
    } else if(idx%5==0) {
      string tmp = "Buzz";
      if(ans.size() + 4 <= 20) {
        ans += tmp;
      } else {
        ans += tmp.substr(0, 20-ans.size());
      }
    } else {
      string tmp = to_string(idx);
      if(ans.size() + tmp.size() <= 20) {
        ans += tmp;
      } else {
        ans += tmp.substr(0, 20-ans.size());
      }
    }
    idx++;
  }
  cout << ans.substr(0, 20) << endl;

  return 0;
}