AOJ-ICPC で無作為に問題を選んで実装する練習をした。あと、桁 DP でやってしまったけど、もっとずっとはるかに楽な方法があった。。。

問題へのリンク

問題概要

1 から順に FizzBuzz をやって得られる文字列を FizzBuzz 文字列と呼ぶ。

12Fizz4BuzzFizz78FizzBuzz11Fizz1314FizzBuzz1617...

と続いていく。整数 s が与えれれて、この文字列の s 番目 (1-indexed) から 20 文字分を出力せよ。

制約

1 <= s <= 10¹⁸

解法

「k 番目を求めよ」
⬇︎
「x 以下の中に k 個あるかどうかを判定する問題にして二分探索」

というのは超典型ではある。この問題もそのフレームワークにガッツリ当てはまる。というわけで、

「1 から x までについて FizzBuzz 文字列を出したときにそれが何文字あるか？」

を求める問題に落ちる。それが解ければ二分探索することで、s 番目が何を出力しようとしていたかがわかる。これを解くのは想定解法は色々頑張るっぽい。自分は桁 DP でやった。

dp[(どの桁まで見たか)][leading zero が何個か][smaller][15 で割った余り] := 個数

ちょっと大変だが、このテーブルを桁 DP によって求めれば、1〜x までの FizzBuzz 文字列が何文字あるのかを計算することができる。

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
using namespace std;

// calc digit-dp
// dp[(桁)][(num of leading-zero)][smaller][15 で割ったあまり] :＝ 個数
long long dp[21][21][3][16];
long long calc(long long num) {
  memset(dp, 0, sizeof(dp));
  dp[0][0][0][0] = 1;
  stringstream ss; ss << num;
  string str = ss.str(); ss >> str;
  for (int i = 0; i < str.size(); ++i) {
    int cur = (int)(str[i] - '0');
    for (int mod = 0; mod < 15; ++mod) {
      // (leading zero = i, exact(0)) ->
      if (cur == 0) dp[i+1][i+1][0][mod*10%15] += dp[i][i][0][mod];
      else dp[i+1][i+1][1][mod*10%15] += dp[i][i][0][mod];
      if (cur != 0) dp[i+1][i][0][(mod*10+cur)%15] += dp[i][i][0][mod];
      for (int c = 1; c < cur; ++c) {
        dp[i+1][i][1][(mod*10+c)%15] += dp[i][i][0][mod];
      }

      // (leading zero = i, smaller(1)) ->
      dp[i+1][i+1][1][mod*10%15] += dp[i][i][1][mod];
      for (int c = 1; c < 10; ++c) {
        dp[i+1][i][1][(mod*10+c)%15] += dp[i][i][1][mod];
      }

      // (leading zero < i, exact(0)) ->
      for (int j = 0; j < i; ++j) {
        dp[i+1][j][0][(mod*10+cur)%15] += dp[i][j][0][mod];
        for (int c = 0; c < cur; ++c) {
          dp[i+1][j][1][(mod*10+c)%15] += dp[i][j][0][mod];
        }
      }

      // (leading zero < i, smaller(1)) ->
      for (int j = 0; j < i; ++j) {
        for (int c = 0; c < 10; ++c) {
          dp[i+1][j][1][(mod*10+c)%15] += dp[i][j][1][mod];
        }
      }
    }
  }

  // num
  long long res = 0;
  for (int j = 0; j < str.size(); ++j) {
    for (int mod = 0; mod < 15; ++mod) {
      if (mod % 3 == 0) continue;
      if (mod % 5 == 0) continue;
      long long num = dp[str.size()][j][0][mod] + dp[str.size()][j][1][mod];
      res += num * ((long long)str.size() - j);
    }
  }

  // fizzbuzz
  long long fizzbuzz = (num/3) * 4 + (num/5) * 4;

  return res + fizzbuzz;
}

int main() {
  long long s; cin >> s;
  
  // 1 から x までの文字列の総数が s 未満となる最大の x を求める
  long long low = 0, high = 1LL<<58;
  while (high - low > 1) {
    long long mid = (high + low) / 2;
    long long all = calc(mid);
    if (all >= s) high = mid;
    else low = mid;
  }

  long long rem = s - calc(low) - 1;
  stringstream ss;
  for (long long i = high; i < high + 20; ++i) {
    if (i % 15 == 0) ss << "FizzBuzz";
    else if (i % 3 == 0) ss << "Fizz";
    else if (i % 5 == 0) ss << "Buzz";
    else ss << i;
  }
  string res = ss.str();
  cout << res.substr(rem, 20) << endl;
}