【Python】AtCorderに立ち向かうためのbit全探索その1

しゅんだい

2020年8月7日 12:11

こんにちは、しゅんだいです(^▽^)/

今日は、全探索について勉強したのでそのポイントと例題についてまとめたいと思います。AtCorder用の勉強は、当面は以下のサイトを用いて行おうと思います。参考に載せておきます。

今回はここに載っているABC079-C-Train Ticketを用いて全探索の考え方と使い方について学習しました。

bit全探索とは

bit全探索とは、「2択によって決められるN個の状態のすべての組み合わせを調べる」というものと捉えています。
ここでいう2択とは、(買う、買わない)や(Yes,No)などにあたり、これを(0,1)に当てはめて組み合わせを考えていきます。

詳しい説明は、Qiitaに優良な記事がたくさんあるのでいくつか紹介して代わりとします。

では、練習問題の解説をしていきます。

問題の設定は読んだ前提でコードを以下に示します。

s = input()

for bit in range(1 << 3):
 ans = int(s[0])
 f = s[0]
 
 for i in range(3):
   if bit&(1 << i):
     ans += int(s[i+1])
     f += "+"
   else:
     ans -= int(s[i+1])
     f += "-"
   f += s[i+1]
 if ans == 7:
   print(f + "=7")
   exit()

この解答コードは、以下の記事から引用しました。

このコードを理解して、自分で書けるようになるまでに恥ずかしながら半日かかったので、ここで丁寧に噛み砕いてみようと思います。

s = input()

では、文字列として標準入力を受け取っています。

for bit in range(1 << 3):

この部分で起きていることを理解するにはまず、bit演算子について知る必要があります。
ここで使われている<<は1を右に3回ずらす、ということです。実際に起きていることを見てみましょう。

1を左に3回ずらすと、(1000)_2という4桁の2進数に変わります。_2は二進数であることを表しています。
つまり、for文で回す範囲は、(1000)_2の1つ前までの(111)_2となります。

全ての範囲について羅列すると、

(0,0,0)
(0,0,1)
(0,1,0)
( ....... )
(1,1,1)
これは+や-が入る箇所をちょうど表すことができます。1を+が入る場所、0を-が入る場所と決めてやると

(0,0,0)→("-","-","-")
(0,0,1)→("-","-","+")
(1,1,1)→("+","+","+")

のように見てやることができるようになります。

ans = int(s[0])
 f = s[0]

の部分は、sとして受け取った数字の文字列はリストとしてみることで各桁ごとにリストの要素としてみなせます。例えば1234を受け取ると、s[0]="1"となり、int(s[0])=1となります。

ここでは、先頭の数字は+や-によって計算する前の合計値となるのでansとします。また、fは最後に出力する数式を表していて、これも先頭の数字はそのまま式においておけばいいので、代入しています。

for i in range(3):
   if bit&(1 << i):
     ans += int(s[i+1])
     f += "+"
　　else:
     ans -= int(s[i+1])
     f += "-"
   f += s[i+1]

まず、for文とif文の意味については合わせて説明します。
上で説明したforでは、(111)_2までの組み合わせで+と-の代入のすべての組み合わせが表現できるという意味がありました。

ここでは、その組み合わせを実際に+と-に置き換える作業をしています。まずif文について説明すると、bitのi桁目の数字が1かどうかという判定をしています。

この仕組みについて簡単に説明すると、
まずbitは(111)_2までの何らかの2進数で表されています。

次に(1<< i)は上記でも説明した通り、1をi回左にずらすというものです。
つまり、i回ずらした位置で1を持つ2進数とbitがAND演算子でYesの判定をもらえばi桁目に1を持つことが言えます。

今、考えている2進数は3桁までなので、1桁目の位置を0としてrangeは3としています。

この判定がYesだった場合には、ansにi+1桁目の数字が足されます。(iは1桁目を0桁目としているため。)また、数式を示すfは”+"が加えられます。

また、判定がNoだった場合には、”-”が入るということなのでansから引き算をし、fに”-”を加えます。

その後、式にi+1桁目の数字を加えて1セットが終わります。

これを繰り返すことで、数式が「”+”または”-”と数字」というセットで追加されていきます。

最後に合計が7になるか確認して満たされれば、プログラムを終了して、満たされなければ続行します。

解説は以上です。どなたかの助けとなれば幸いです。説明が間違っている場合には、ご指摘ください。

この記事が気に入ったらサポートをしてみませんか？