記事の概要
自分の勉強兼メモでまとめている記事シリーズです。第四弾。
こちらの記事の続きです。
javaでアルゴリズム入門 - 探索編（幅優先探索）
今回の記事では
- bit全探索
について勉強します。
演算の解説もしっかり目にやってるので是非。
bit全探索
ちょっと前までこれがバイナリサーチのことだと思ってましたが違うみたいですね。
どんな探索なのかというところから調べてみましょうか。
調べてみました。
ある集合の中の一つ一つに対して（多分）2択の選択肢があるとき、全パターンを探索するときのやり方のようです。
わかりづらいですかね？さっそくではありますが例題を紹介します。
例：AtCoder - abc167-c「Skill Up」
（セクション開始） 【制約】 【入力】 【出力】 （セクション終了）問題文・入力例などはここをクリックして表示
※できるだけ問題リンクを参照してください
【問題文】
競技プログラミングを始めた高橋くんは、学びたいアルゴリズムが M 個あります。 最初、各アルゴリズムの理解度は 0 です。
高橋くんが書店に行くと、N 冊の参考書が売っていました。i 番目の参考書 (1≤i≤N) は Ci 円で売られていて、購入して読むことで、各 j(1≤j≤M) について j 番目のアルゴリズムの理解度が Ai,j 上がります。 また、それ以外の方法で理解度を上げることはできません。
高橋くんの目標は M 個すべてのアルゴリズムの理解度を X 以上にすることです。高橋くんが目標を達成することが可能か判定し、可能な場合は目標を達成するのに必要な金額の最小値を計算してください。
入力はすべて整数
1≤N,M≤12
1≤X≤10^5
1≤Ci≤10^5
0≤Ai,j≤10^5
入力は以下の形式で標準入力から与えられる。N M X
C1 A1,1 A1,2 ⋯ A1,M
C2 A2,1 A2,2 ⋯ A2,M
⋮
CN AN,1 AN,2 ⋯ AN,M
高橋くんが目標を達成できないならば -1 を、 そうでなければ目標を達成するのに必要な金額の最小値を出力せよ。
この問題みたいに、i番目の本を「買う・買わない」の2択になっているところがthe・bit全探索問題みたいな感じです。
参考書はN冊あり、1冊1冊について「買う・買わない」の2択を決めますので、2^N回の探索が必要になるという事ですね。
↓
| 1冊目 | 2冊目 | 3冊目 | 4冊目 | ・・・ | N冊目 |
|---|---|---|---|---|---|
| 買う or 買わない |
買う or 買わない |
買う or 買わない |
買う or 買わない |
買う or 買わない |
買う or 買わない |
この通りですね。N冊それぞれに対して2択があるので2^N通りです。
ここで、買う = 1 , 買わない = 0とすると、2進数チックに表す事ができます。
桁上位からN,N-1,N-2,...,3,2,1冊目とすると、例えばN=5のとき、
「01001」は4冊目と1冊目を買うという意味ですね。
ちなみに数学的にいうと、「参考書N冊の購入是非の部分集合の個数」とも言えます。
参考書N冊の集合を{1,2,3,...,N-1,N}とすると、例えば1冊目と3冊目を買うときの部分集合は{1,3}と表せますね。
この「部分集合の個数」も2^Nで表せます。「部分集合に加えるのか加えないのか」の2択を各参考書（このときの参考書のことを数学的には元とか要素とかいいます）に適用すれば良いので。
例えば3冊の購入是非の部分集合は以下の通りとなります。
{000}・・・1冊も買わない
{001}・・・1冊目だけ買う
{010}・・・2冊目だけ買う
{011}・・・1冊目と2冊目を買う
{100}・・・3冊目だけ買う
{101}・・・1冊目と3冊目を買う
{110}・・・2冊目と3冊目を買う
{111}・・・3冊すべて買う
ちょうど2^3 = 8通りとなることがよくわかりますね。
ではjavaの回答例を見てみましょう。
【回答例】
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 参考書数
int n = sc.nextInt();
// 習得したいアルゴリズム数
int m = sc.nextInt();
// 習得目標理解度
int x = sc.nextInt();
// n番目の参考書の値段
int[] costs = new int[n];
// n番目の参考書のm番目のアルゴリズムの上昇理解度
int[][] a = new int[n][m];
// 入力の受け取り
for (int i = 0; i < n; i++) {
costs[i] = sc.nextInt();
for (int j = 0; j < m; j++) {
a[i][j] = sc.nextInt();
}
}
// m番目のアルゴリズムの理解度、参考書コストのtmp変数と、loop毎の参考書コストを覚えておく変数、アルゴリズム習得達成したかの変数
int[] aTmp = new int[m];
int costTmp = 0;
List<Integer> costsSave = new ArrayList<>();
boolean mastered = true;
/*
* ここからbit全探索
*/
for (int i = 0; i < 1 << n; i++) {
// bit全探索の全通りのloop
for (int j = 0; j < n; j++) {
// 1loop毎にどの参考書を買うかの判定(j冊目を買うかどうか)
if ((1 & i >> j) == 1) {
// ここに引っかかった = 買う対象に追加(j冊目購入)
for (int h = 0; h < m; h++) {
// j冊目の参考書を買ったときのm番目のアルゴリズムの理解度上昇
aTmp[h] += a[j][h];
}
// j冊目の値段
costTmp += costs[j];
}
}
// 参考書を買い終わったので、アルゴリズムを覚えられたかどうかの判定の上、値段を保持
for (int h = 0; h < m; h++) {
if (aTmp[h] < x) {
// アルゴリズムを1つでも覚えられていない場合、NG
mastered = false;
break;
}
}
if (mastered) {
// 合計値段を一時格納
costsSave.add(costTmp);
}
// 後始末
for (int h = 0; h < m; h++) {
aTmp[h] = 0;
}
costTmp = 0;
mastered = true;
}
// listのうち最小の値を出力。リストがnullなら"-1"を出力
int ans = Integer.MAX_VALUE;
if (costsSave.isEmpty()) {
ans = -1;
} else {
for (int cost : costsSave) {
if (ans > cost) {
ans = cost;
}
}
}
System.out.println(ans);
}
}
こんな感じです。なにやら普段javaを書いているときには見慣れない記号を2回くらい使ってますね。
「ここからbit全探索」ってところの
for (int i = 0; i < 1 << n; i++)
と、
「ここに引っかかった = 買う対象に追加(j冊目購入)」の
if ((1 & i >> j) == 1)
ですね。
「&」「<<」「>>」は「bit演算子」と呼ばれています。
詳しい処理は ggっていただいて、簡単に説明しますと、「&」は論理積、「<<」や「>>」はbit列を右または左にシフトをするものです。
（例）
01001 & 11000 = 01000
01001 << 1 = 10010
00100 >> 1 = 00010
bit毎の論理積を取る、右や左へのシフトがわかったでしょうか。ここはさらっといきます。
ではコードの説明をします。
まずは
for (int i = 0; i < 1 << n; i++)
こちらです。
このfor文の繰り返し条件の部分、i < 1 << nに注目しましょう。
まず最初の記号"<"（iの右にあるやつ）は不等号で間違いなさそうです。
で、1 << n の「<<」がbit演算子（厳密にいうとシフト演算子）です。
1 << nの意味ですが、「1をn回左にシフト」を意味しています。
例えば1を1回左にシフトすると、「10」です（2進法で表しています。10進法だと2ですね）。
同様に
1を2回左にシフトすると、「100」です（2進法で表しています。10進法だと4(=2^2)ですね）。
1を3回左にシフトすると、「1000」です（2進法で表しています。10進法だと8(=2^3)ですね）。
1を4回左にシフトすると、「10000」です（2進法で表しています。10進法だと16(=2^4)ですね）。
イメージ
そもそも今回の全探索の回数としては、n冊の参考書対して買う・買わないの通りなので2^N通りを考えたかったのですね。つまりこのfor文を書き換えると、
for (int i = 0; i < Math.pow(2,n); i++)
とも書き換えられるわけです。なんとなく分かったでしょうか。
では次にいきます。
if ((1 & i >> j) == 1)
これがわかりづらかったんですよね。。
if文のカッコの中を日本語に直すと「1と i>>j の論理積が1と等しいかどうか」です。
例えばi=5、j=2としましょう。
（この問題的にいうと5回目の探索、3冊目の購入是非の検討をしている途中です。）
5を二進数に直すと0101、これを2回右シフトすると以下のような感じです。
で、これと1（0001）の論理積をとります。1と論理積を取るということは、最下桁が1かどうかを判定していることがわかりますでしょうか。
2回シフトして最下桁が1ということは言い換えると最下桁から2個左を見て1かどうかを見ているわけですね。つまり下からj桁目が1かどうかを判定しているわけです。それが1だったら購入の対象とする、と言った感じです。
「ここからbit全探索」のところのfor文で全パターンの探索、
次のfor文「1loop毎にどの参考書を買うかの判定(j冊目を買うかどうか)」でそのパターンで買う本の特定をしているわけです。
ちょっと難しいですかね。
試しに具体的な入力例を入れて処理を追ってみましょうか。
【入力例】
3 3 10
60 2 2 4
70 8 7 9
50 2 3 9
n = 3 , m = 3 , x = 10
0冊目のコスト、アルゴリズムの理解度0,1,2
1冊目のコスト、アルゴリズムの理解度0,1,2
2冊目のコスト、アルゴリズムの理解度0,1,2
の順番でしたね。わかりやすく0スタートで数えてます。
じゃあbit全探索いきましょう。
n = 3なので、
「ここからbit全探索」のloopは
for(int i = 0 ; i < 1 << 3 ; i++)
で、1 << 3は、0001を3回左にシフトするので1000となります。つまり8ですね。
ぴったり2^3になっています。
i = 0 から i = 7 まで順番に見てみましょう。適宜二進数に直していきます。
jで見ようとしている桁を太字で表しています。
i = 0（000）のとき
j = 0のとき（i = 000）
if ((1 & 000 >> 0) == 1)ではないため、0冊目は買わない
j = 1のとき（i = 000）
if ((1 & 000 >> 1) == 1)ではないため、1冊目は買わない
j = 2のとき（i = 000）
if ((1 & 000 >> 2) == 1)ではないため、2冊目は買わない
i = 1（001）のとき
j = 0のとき（i = 001）
if ((1 & 001 >> 0) == 1)であるため、0冊目は買う
j = 1のとき（i = 001）
if ((1 & 001 >> 1) == 1)ではないため、1冊目は買わない
j = 2のとき（i = 001）
if ((1 & 001 >> 2) == 1)ではないため、2冊目は買わない
i = 2（010）のとき
j = 0のとき（i = 010）
if ((1 & 010 >> 0) == 1)ではないため、0冊目は買わない
j = 1のとき（i = 010）
if ((1 & 010 >> 1) == 1)であるため、1冊目は買う
j = 2のとき（i = 010）
if ((1 & 010 >> 2) == 1)ではないため、2冊目は買わない
i = 3（011）のとき
j = 0のとき（i = 011）
if ((1 & 011 >> 0) == 1)であるため、0冊目は買う
j = 1のとき（i = 011）
if ((1 & 011 >> 1) == 1)であるため、1冊目は買う
j = 2のとき（i = 011）
if ((1 & 011 >> 2) == 1)ではないため、2冊目は買わない
i = 4（100）のとき
j = 0のとき（i = 100）
if ((1 & 100 >> 0) == 1)ではないため、0冊目は買わない
j = 1のとき（i = 100）
if ((1 & 100 >> 1) == 1)ではないため、1冊目は買わない
j = 2のとき（i = 100）
if ((1 & 100 >> 2) == 1)であるため、2冊目は買う
i = 5（101）のとき
j = 0のとき（i = 101）
if ((1 & 101 >> 0) == 1)であるため、0冊目は買う
j = 1のとき（i = 101）
if ((1 & 101 >> 1) == 1)ではないため、1冊目は買わない
j = 2のとき（i = 101）
if ((1 & 101 >> 2) == 1)であるため、2冊目は買う
i = 6（110）のとき
j = 0のとき（i = 110）
if ((1 & 110 >> 0) == 1)ではないため、0冊目は買わない
j = 1のとき（i = 110）
if ((1 & 110 >> 1) == 1)であるため、1冊目は買う
j = 2のとき（i = 110）
if ((1 & 110 >> 2) == 1)であるため、2冊目は買う
i = 7（111）のとき
j = 0のとき（i = 111）
if ((1 & 111 >> 0) == 1)であるため、0冊目は買う
j = 1のとき（i = 111）
if ((1 & 111 >> 1) == 1)であるため、1冊目は買う
j = 2のとき（i = 111）
if ((1 & 111 >> 2) == 1)であるため、2冊目は買う
いかがでしょうか？ちょうど1になっている桁だけ買う、とできていますね。
買う参考書がどれかわかったらあとは計算するだけなのでそこの処理については飛ばしますね。
書いてる私もいざ実装して、と言われたら実装できなさそうなのであとは練習です。
AtCoderの以下の問題とか練習になるのであとで解こうと思います。練習あるのみ！！！
AtCoder - abc079-c「Train Ticket」
AtCoder - abc128-c「Switches」
いったんここまでで探索編は終わりにします。
全探索、二分探索、深さ優先探索、幅優先探索、bit全探索について勉強してきましたがいかがでしょうか。興味のある方はリンクを追ってみてくださいね。
ちょっと練習期間ということでこれらの探索を練習したら今度はDPやダイクストラについても勉強していけたらな、と思います。
お付き合いいただきありがとうございました。それでは。