アルゴリズムの技　bit全探索　を習得して　巨大な探索網に挑め！

投稿日：2019年12月9日

巨大な探索網とは

2^Nで構成される木のことです。

bit全探索とは、N個のintからなる配列Sが与えられた時の、和の最大を答えよ

と言われた時、

愚直にBFをかんがえると、i個目のintを取る・取らないの２値で組み合わせが決まり

その合計のすべて比較すればよい。

このときの探索スペースは2^Nである。

このbit全探索に私が出会ったきっかけは

abc147_cのHonestOrUnkind2という問題である。

これは解けなくて、悔しい思いをしました。解説を見てもよくわからないので

知らない単語「bit全探索」を知ることから始めないといけませんでした。

解説はこちら

N 人の人がそれぞれ正直者であるか不親切な人であるかを決めれば, その状態が証言と矛盾しないかは, O ( N2 ) で容易に確かめることが出来ます. N 人の人がそれぞれ正直者か否かについては全部で 2 N 通りしかありませんから, これら全ての場合について矛盾が生じないかを調べ, 矛盾が生じないうちでの正直者の最多人数を答えとすれば良いです. 実装上は, 0 以上 2 N 未満の整数 j が「1 以上 N 以下の整数 k について, 人 k が正直者であることと, j を 2 進数表記した際に k − 1 桁目が 1 であることが同値」という状態を表すことと定義すると, 容易に全ての場合を試すことが出来ます. この手法はbit 全探索と呼ばれています. C++ による解答例:https://atcoder.jp/contests/abc147/submissions/8830089

uh-huh(mあ〜ハン)　って感じではて?となりました。

それでも0001, 0010, 0011って単純な整数のインクリで2^Nが表現できてそうやん！という、

うわぁ、よくわからないけどなんとく凄そう！感は感じることができました。

もうすこし簡単な問題からやりたいやん、ということで

Train Ticket 079C行ってみましょう。

実際に実装してみると、よく身につきます。bit全探索で網羅できるのはよくわかった。

だけどこれを、それぞの問題に合わせて表現するのは結構難しい。今回であれば足し算と引き算を構成する部分。これは慣れだろうか。

def sol(a, b, c, d):
    S = [a, b, c, d]
    for i in range(1<<3):
        ttl = a
        ans = "%s" % a
        for j in range(3):
            if i & (1 << j): # '+'
                ttl += S[j+1]
                ans += "+%s" % S[j+1]
            else:
                ttl -= S[j+1]
                ans += "-%s" % S[j+1]
        if ttl == 7:
            return ans+"=7"
        else:
            assert(True)

はい。これをbit全探索の基本形として

abc147_cのHonestOrUnkind2に再挑戦してみます。

bit全探索は英語ってなんて言うんでしょうか。ググってもでてきませんでした。

def sol(N, testimonies):
    # print(N)
    # print(testimonies)
    maxi = 0
    for i in range(1<<N):
        ok = True
        for j in range(N):
            for x, y in testimonies[j]:
                if i & (1 << j): #正直者
                    if i & (1 << (x-1)) and not y: # 正直者と行っており、そうじゃないやん
                        ok = False; break
                    elif not (i & (1 << (x-1))) and y: #嘘つきといってるけど、そうじゃないやん！
                        ok = False; break
            if not ok:
                break
        if ok:
            maxi = max(count1(i), maxi)
    return maxi

２つくらいやると、bit全探索が感覚がつかめてきました。

このあとの練習はatcoder Programming guide for beginner( APG4bのbit演算）にも

ある

をやってみるとさらに、対応できるスピードと範囲が広がると思いますので

時間のある人はやってみるといいと思います。

以上です。

参考参照：

https://qiita.com/Namu3/items/be038733786dea21dfa2

atcoder Programming guide for beginner( APG4bのbit演算）

アルゴリズムの技 bit全探索 を習得して 巨大な探索網に挑め！

アルゴリズムの技　bit全探索　を習得して　巨大な探索網に挑め！