全探索

Last renew: May 14, 2022 pm

　この記事は、日本語やプログラミングスキルを向上するために書きました。著者は中国出身ですから、言語、文法のミスがいっぱいあるかもしれない…

全探索のまとめ（自分用）

　全探索とは、中国語”暴力解法”と言います。多分計算量や時間複雑性はすごく高い、アルゴリズム全然使えない方法です。全探索を選択する前、必ずTime Complexityを確認してください。（P.S. 競プロについて、計算量は 10^8 ~ 10^9 回数のループを越えれば、ACはできません）

　ビット全探索と順列全探索は別のものです！普通の問題に対して、データが10個以下の場合は順列全探索を、20個以下の場合はビット全探索を使えます。

　普段な全探索は、四つの種類があります：

  1. 本当に　”全部を調べる”　の全探索
  2. なるべく探索の数を減らすの全探索
  3. ビット全探索
  4. 順列全探索

本当に”全部を調べる” の全探索

　それは普通です、普通のfor/whileループを使って（二層ループの場合もある）コードを書くだけです。

例：ABC144B、ABC150B、ABC122B、ABC136B、ABC106B、ABC120B

（ABCに対してレベルBの感じ）

なるべく探索の数を減らすの全探索

　”全部を調べる”の全探索より探索数を減らす方法です。今僕を書いた問題は代々”全部を調べる”ことはできないの場合（TLE、ループ回数を超える）、そいよう方法を考えようと思っています。

　多分探索したのことを二度と探索しないのために、順列やハッシュなどのデータ構造を使って探索したことを記録します。

例：ABC057C、ABC095C、三井住友信託銀行プログラミングコンテスト2019 D - Lucky PIN

（ABCに対して簡単なレベルCの感じ）

ビット全探索

　初めて知りましたの全探索の種類、ブログ記事に勉強しています。代々みんなはCPPを使って競プロをやります（プログラミング速度を上がくため）。僕はJavaやPythonを使った場合が多いので、多分CPPを練習しようと思っています。

　ビット全探索とは、二進数とビットを用いて、ある集合の部分集合を全列挙（全探索）するアルゴリズムのこと。

基礎（Javaに対して）：

  1. i >> j：iの桁をjビット右シフトする

    例１：6 >> 3

    　0000 0000 0000 1010（6）右シフト3

    　結果：0000 0000 0000 0001（1）

　　例２：-92 >> 2

　　　1111 1111 1111 1111 1111 1111 1010 0100

​ 　0011 1111 1111 1111 1111 1111 1110 1001（1073741801）

  1. &：論理積。左右双方の式にセットされているビット。対応するビットが両方とも1の場合，結果は1，それ以外の場合は0となる。

　　例１：0011 1100 & 0000 1101

　　　0011 1100 (60)

​ 0000 1101 (13)

　　　結果：0000 1100 (12)

ビット全探索コード例：

1
2
3
4
5
6
7
8
9
10
String[] ar = {"a","b","c"};
		int n = 3;

for (int i=0; i<(Math.pow(2,n)); i++) {
			String s = "-";
			for (int j=0; j<n; j++) {
				if ((1&i>>j) == 1) {s += ar[j];}
			}
			System.out.println(s);
		}

入力：String {a, b, c}

出力：-a, -b, -ab, -c, -ac, -bc, -abc

例：ABC128C、ABC147C

順列全探索

　順列全探索とは、決まった数字や文字の列の全ての順列を出力します。時間複雑性はN!ですから、普通は10以下のことを計算すると思います。