いいものをつくろう

CTOの日記

アルゴリズム

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

投稿日:

巨大な探索網とは

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

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

と言われた時、

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

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

このときの探索スペースは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

 

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

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

ある

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

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

 

以上です。

 

 

 

 

参考参照:

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

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

 

 

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.