Static bitset size dispatch （コンパイル時 bitset サイズの実行時分岐）
(utilities/static_bitset_size_dispatch.hpp)

• View this file on GitHub
• Last update: 2026-03-01 21:22:12+09:00
• Include: #include "utilities/static_bitset_size_dispatch.hpp"
• Link: https://codeforces.com/blog/entry/143059

実行時に決まるサイズ $n$ に対して，$n$ 以上の最小のコンパイル時定数をテンプレート引数として std::bitset 等を利用できるようにするユーティリティ．サイズの候補は $1$ から約 $\alpha = 1.5$ 倍ずつ増加し，$2^{30}$ を上限とする．

使用方法

static_bitset_size_dispatch(n, [&]<size_t BS_SIZE>() {
    std::bitset<BS_SIZE> bs;
    // BS_SIZE >= n が保証される
});

• n: 必要なビットサイズ（unsigned long long）．
• callback: テンプレート引数 BS_SIZE（n 以上のコンパイル時定数）を受け取るジェネリックラムダ．

コンパイル時にサイズ候補ごとのインスタンスが生成される．増加率を $\alpha$ として， n がおおよそ $2^{30} / \alpha$ 以上の場合は何も実行されない可能性がある．

問題例

• Codeforces Round 1079 (Div. 1) E2. Fuzzy Concatenation (Hard version)
  • Submission #362639741 - Codeforces

リンク

• Variable size bitset (kind of) - Codeforces

Code

#pragma once

// https://codeforces.com/blog/entry/143059
template <unsigned long long sz = 1>
void static_bitset_size_dispatch(unsigned long long n, auto &&callback) {
    if constexpr (sz > (1ULL << 30)) {
        return;
    } else if (n > sz) {
        static_bitset_size_dispatch<((sz * 3 + 1) / 2)>(n, callback); // tune here
    } else {
        callback.template operator()<sz>();
    }
}
/* Usage:
int ret = 0;
static_bitset_size_dispatch(n, [&]<size_t BS_SIZE>() {
    std::bitset<BS_SIZE> bs;
    // do something...
    // ret = ...;
});
*/

#line 2 "utilities/static_bitset_size_dispatch.hpp"

// https://codeforces.com/blog/entry/143059
template <unsigned long long sz = 1>
void static_bitset_size_dispatch(unsigned long long n, auto &&callback) {
    if constexpr (sz > (1ULL << 30)) {
        return;
    } else if (n > sz) {
        static_bitset_size_dispatch<((sz * 3 + 1) / 2)>(n, callback); // tune here
    } else {
        callback.template operator()<sz>();
    }
}
/* Usage:
int ret = 0;
static_bitset_size_dispatch(n, [&]<size_t BS_SIZE>() {
    std::bitset<BS_SIZE> bs;
    // do something...
    // ret = ...;
});
*/

Back to top page