結果

問題 No.294 SuperFizzBuzz
コンテスト
ユーザー tubo28
提出日時 2015-12-26 20:53:49
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 62 ms / 5,000 ms
コード長 1,574 bytes
コンパイル時間 537 ms
コンパイル使用メモリ 63,120 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-19 00:36:59
合計ジャッジ時間 1,555 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘std::string solve()’:
main.cpp:76:35: warning: ‘ans’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |         res = string() + "35"[ans >> i & 1] + res;
      |                               ~~~~^~~~

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <string>
#include <cstring>

using namespace std;

using ll = long long;

/*
5で終わって各桁の和が３の倍数
5は2, 3は0
5が3の倍数個
*/

ll n;

ll nCr(int n, int r) {
    static bool done[50 + 1][50 / 2 + 2];
    static ll dp[50 + 1][50 / 2 + 2]; // 400MB
    if (n < 0 || r < 0 || n < r) return 0;
    if (r == 0) return 1;
    if (r > n - r) r = n - r;
    ll &res = dp[n][r];
    if (done[n][r]) return res;
    done[n][r] = true;
    return res = nCr(n - 1, r - 1) + nCr(n - 1, r);
}

ll count(ll w) {
    ll res = 0;
    for (int i = 2; i <= w - 1; i += 3) {
        res += nCr(w - 1, i);
    }
    return res;
}

int pc(int s) {
    static int memo[65555];
    if (memo[1] == 0) {
        for (int i = 0; i < 65555; ++i) {
            memo[i] = memo[i / 2] + i % 2;
        }
    }
    return memo[s & 0xFFFF] + memo[s >> 16];
}

string solve() {
    --n;
    ll acc = 0;
    int w = 1;
    while (1) {
        if (acc + count(w) <= n) {
            acc += count(w);
            w++;
        }
        else {
            break;
        }
    }
    int k = 0;
    ll ans;
    for (int S = 0; S < 1 << w; ++S) {
        if (S & 1 && pc(S) % 3 == 0) {
            if (k == n - acc) {
                ans = S;
                break;
            }
            k++;
        }
    }
    string res;
    for (int i = 0; i < w; i++) {
        res = string() + "35"[ans >> i & 1] + res;
    }
    return res;
}

int main() {
    while (cin >> n) cout << solve() << endl;
}
0