僕が考えたこととライフハック

自分がやったこととか、経験したことを書いていく。プログラミング、サークル運営、学校生活etc..

#3競プロ bit全探索について Java

こんにちは。

bit全探索がわかってきたので、メモしとこうと思います。

ほんんんとうの初学者の方向けなのでかなり細かく、冗長に書いていますのでよろしくお願いいたします

bit全探索とは

全探索する手法の一つで「要素を選ぶか否かを2進数で表し、漏れなく調べ上げる」というものです。

言葉だとわかりにくいと思うので、実際のコードを見ながら理解していこうと思います。

 

Javaのbit演算子のおさらい

i  << 3  ・・・i を左に3ビットシフト

i  >> 3  ・・・i を右に3ビットシフト(符号あり)

i >>>3  ・・・i を右に3ビットシフト(符号なし)

 

ビットシフトがわからないという方は↓

https://www.grapecity.com/developer/support/powernews/column/clang/019/page02.htm

解く問題

ABC045 - C TrainTicket

https://atcoder.jp/contests/abc079/tasks/abc079_c

問題を読んでおくと理解が深まると思います。

書いたコード

ABC045 - C

コード説明

問題を読んでみると、調べる回数は2^3通りしかないのでif文で全部列挙してしまえば簡単なのですが、今回はわざとbit全探索で解いてみました。

2進数で”+”か”-”かを選んでいく

0~7までの2進数をいったん書いてみましょう。2進数の後ろには(2)と書いていきます。

0 = 000(2)

1 = 001(2)

2 = 010(2)

3 = 011(2)

4 = 100(2)

5 = 101(2)

6 = 110(2)

7 = 111(2)

となります。

これらを活用してプラスを選ぶのか、マイナスを選ぶのかを考えていきます。

 

0→マイナス。

1→プラス。を表していると考えて下さい。

入力が1222の時

0 = 000(2) → 1 - 2 - 2 - 2 = -5

1 = 001(2) → 1 - 2 - 2 + 2 = -1

2 = 010(2) → 1 - 2 + 2 - 2 = -1

3 = 011(2) → 1 - 2 + 2 + 2 = 3

4 = 100(2) → 1 + 2 - 2 - 2 = -1

5 = 101(2) → 1 + 2 - 2 + 2 = 3

6 = 110(2) → 1 + 2 + 2 - 2 = 3

7 = 111(2) → 1 + 2 + 2 + 2 = 7 (答えはすべて+の時だ!!)

という風に全通り表現することができます。 

 

5~10行目:入力された4桁の数字を文字列として受け取り一文字ずつ配列nに入れていく.

そのあと、文字列を数字に変換し、numという1桁ずつ数字が格納された配列を作る。

12行目:上でも書いた通り、全部で2の3乗通りなので8回ループします。もし、それ以上ループする必要があるならば(桁数が決まっていない時は) Math.pow( 2 , num.size) で良いでしょう。

14行目:この問題では文字列を出力しなければいけないので”+”,”ー”の符号をつなげるための文字列変数sを作ります。

15行目~:上の画像1で示したように、どのくらいシフトするのかをループで回さなければいけないのでこのように書きました。

j = 0 , 1 , 2 とそれぞれ、右に0,1,2個シフトする。という感じです。

そしてif文の判定

if(( 1 & i >> j ) == 1)

 これがよくわからんと思いますが、ここでは、表現した2進数の0,1を判定しています。

 i = 〇、j = 〇のとき・・・と書いてみるとわかってくると思います。

んで、1のときif文はTrueを通る。1は”+”なので足します。

0のときif文はFalse、つまりelseを通るので"ー"の処理をします。

 

24行目:合計が7だったらその時の文字列sを出力して終了!

といった感じです。

 

まとめ

処理が2択のときはbit全探索!!!