Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

競プロでよく出るbit全探索について初心者の目からpythonで

初めに

競プロをしていてアルゴリズムの勉強を始めました。
アルゴリズムの初歩であるbit全探索についてアウトプットの意味も込めて解説しようと思います。
まだまだ浅学の身ですので誤りがあればどんどんご指摘ください。
競プロの話メインで書いていきます。

bit全探索とは

全探索の手法の一つです。
複数の変数が存在し、それぞれの変数が二通りの値をとるときにこの手法は使えます。
bitとはコンピュータにおける0と1のことで二通りの値をとることをbit
になぞらえています。
文字の説明じゃわかりづらいと思うので、例題を乗っけておきます。

例題

0,1
の2数字のみをリストに入れることができる。
リストの長さは3である。
考えられるリストをすべて挙げよ。

解答

bit.py
for i in range(2**3): #1
    list=[0]*3 #2
    for k in range(3): #3
        if ((i>>k)&1): #4
            list[k]=1 #5
    print(list)

解説

1 リストのそれぞれの要素は1か0の2通りなので要素の数は2**(要素の個数です)
2 仮のリストを作成しておきます。後でbit演算の結果に応じて書き換えます。 ちなみに[0]*3=[0,0,0]です。
3 リストの長さは3なので最大2回ずらせます
4  bit全探索の核心部分です。
i >> kは、iをk回左シフトさせるという意味です。
&はandを示すので、この行は「i >> kは、iをk回左シフトさせると1がTrueならば」という意味です。

競プロでの例題

https://atcoder.jp/contests/abc045/tasks/arc061_a

重要なこと

#2をforループの上に持ってこない
#4はbit演算子
#& はbit演算の論理積、ついでに|は論理和、^は排他的論理和

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away