競プロで制約が極端に小さいとき大体bit全探索で解ける説

何の話？

競技プログラミング（AtCoder）において、問題の制約が$N \leq 10$とかの極端に小さい場合はbit全探索で解けないかを疑ったほうがいい。

その根拠は、$2^N$は$N=30$くらいで結構大きな数になる点である。

$2^{10} = 1024 \fallingdotseq 10^3$

$2^{20} = 1048576 \fallingdotseq 10^6$

$2^{30} = 1073741824 \fallingdotseq 10^9$

$2^{40} = 1099511627776 \fallingdotseq 10^{12}$

AtCoderの場合は御存知の通り実行時間が2秒以内と決められており、言語によるがおおよそ$O(10^8)$までに計算量を抑えておくことが望ましい。（pythonは激遅なので$O(10^6)$くらいにビビっておいたほうがいい）

なので、bit全探索の問題をAtCoderで出題しようと思うとせいぜい$N\leq20$くらいに抑えておかないと実行時間制約的に作問できないわけである。

特に、AtCoderのCD問題で$N \leq 10, M \leq 15$とかの制約が与えられたときはとても怪しい。
以下、具体例を挙げていく。

（AB問題で$N\leq10$とかの場合はただの虚無問題である可能性があるため一概にbit全探索とは言えない）
（EF問題は知らない）

AtCoder Beginner Contest 128 C - Switches

問題リンク：https://atcoder.jp/contests/abc128/tasks/abc128_c

N個のスイッチとM個の電球に関する問題。
注目すべきは$1 \leq N, M \leq 10$という制約。

小さい。あまりにも小さい。怪しい。

$2^N \leq 1024$ なので、全スイッチのON/OFFパターンを列挙してもおよそ高々$10^3$通りということになる。
それぞれのパターンについて全電球を調べ、ONのスイッチ個数の偶奇を調べる。

以下はPythonでも実装例。

n, m = map(int, input().split())
s = []
k = []
for i in range(m):
    s.append(list(map(int, input().split())))
    k.append(s[i].pop(0))
p = list(map(int, input().split()))

# 全点灯パターンの個数
ans = 0

# 点灯している電球の数
cnt_s_on = 0

# 電球jに繋がるONのスイッチの数
cnt_switch = 0

for i in range(2**n):
    cnt_s_on = 0

    # すべての電球に対して調べる
    for j in range(m):
        cnt_switch = 0

        # 電球jに繋がるすべてのスイッチに対してON/OFFを調べる
        for K in range(k[j]):
            if ((i >> (s[j][K]-1)) & 1):
                # スイッチがONならONカウントに＋する
                cnt_switch += 1

        if cnt_switch%2 == p[j]:
            # 電球jは点灯している
            cnt_s_on += 1

    if cnt_s_on == m:
        ans += 1

print(ans)

AtCoder Beginner Contest 167 C - Skill Up

問題リンク：https://atcoder.jp/contests/abc167/tasks/abc167_c

参考書がN冊あり、条件を満たしてくれる最小の支払価格を求める問題。
こちらも$1 \leq N, M \leq 12$と小さい。
$2^N \leq 4096$なので、時間内に全探索できることがわかる。

参考書の選び方それぞれについて、アルゴリズムの理解度を計算し、条件を満たしていればその時の支払価格をチェックする。

以下はPythonでの実装例。

n, m, x = map(int, input().split())
ca = []
for _ in range(n):
    ca.append(list(map(int, input().split())))

INF = float("inf")
ans = INF

for i in range(2**n):
    A = [0] * m
    price = 0

    # j番目の本について
    for j in range(n):
        if i>>j & 1:
            price += ca[j][0]
            for k in range(m):
                A[k] += ca[j][k+1]

    # X以上かどうか
    gtX = True

    for j in range(m):
        if A[j] < x:
            gtX = False
            break
    if gtX:
        ans = min(ans, price)

# 目標を達成できない場合
if ans == INF:
    ans = -1
print(ans)

ALDS_5_A - 総当たり

問題リンク：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=ja

AtCoderではないですが、同じことが言えるので。
こちらも$N \leq 20$なので、bit全探索を疑う。

数列Aの要素の選び方を全列挙し、その時の総和を記録しておく。
その後各mについてチェックしてyes/noを出力すればOK.

以下はPythonでの実装例。

n = int(input())
a = list(map(int,input().split()))
q = int(input())
m = list(map(int,input().split()))

cnt = [0] * (2000 * 20)

for i in range(1, 2**n + 1):
    SUM = 0
    for j in range(n):
        if i>>j & 1:
            SUM += a[j]
    cnt[SUM] = 1

for _m in m:
    if cnt[_m] == 1:
        print("yes")
    else:
        print("no")

さいごに

この説はあくまで筆者の勘です。
制約が小さくてもbit全探索以外で解ける問題もこの世にはあると思います。