ひとりで勝手にはじめた蟻本読書会の続きです。
基本は全探索
競技プログラミングにおけるすべての基本は全探索です。といってもfor 文を二重三重にして回すだけでは全探索を理解したことにはなりません。bit全探索や深さ優先探索、幅優先探索なども絶対に外せない全探索のテクニックです。
部分和問題
Lake Counting
迷路の最短路
特殊な状態の列挙
普通の全探索
駅の待合室に座っているjoisinoお姉ちゃんは、切符を眺めています。
切符には 4 つの 0 以上 9 以下の整数 A, B, C, D が整理番号としてこの順に書かれています。
A op1 B op2 C op3 D = 7 となるように、op1, op2, op3 に + か – を入れて式を作って下さい。
答えが存在しない入力は与えられず、また答えが複数存在する場合はどれを出力してもよいものとします。
for 文を二重三重にして回すだけの普通の全探索です。 + か – を入れる部分は3個所しかないので三重ループで対応します。ループの変数 a, b, c で + か – を決め、あとは計算して 7 になるか調べているだけです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int[] vs = Console.ReadLine().ToArray().Select(_ => int.Parse(_.ToString())).ToArray(); for (int a = 0; a < 2; a++) { for (int b = 0; b < 2; b++) { for (int c = 0; c < 2; c++) { int ret = vs[0]; ret = a == 0 ? ret + vs[1] : ret - vs[1]; ret = b == 0 ? ret + vs[2] : ret - vs[2]; ret = c == 0 ? ret + vs[3] : ret - vs[3]; if (ret == 7) { string op1 = a == 0 ? "+" : "-"; string op2 = b == 0 ? "+" : "-"; string op3 = c == 0 ? "+" : "-"; Console.WriteLine($"{vs[0]}{op1}{vs[1]}{op2}{vs[2]}{op3}{vs[3]}=7"); return; } } } } } } |
部分和問題
部分和問題とはこんな問題です。
int型の配列 A が与えられます。そのなかからいくつかの要素を選びその和をちょうど K にすることはできるでしょうか？
A[0]から順番に追加するかどうかを深さ優先探索で全探索します。
i 個（A[0] ～ A[i-1]）追加するしないを決めたときの 和 sum は K と等しいかを返すメソッドを定義して再帰呼び出しします。この場合、計算量は O(2^n) となります。なので配列が長くなるとこの方法ではなく別の方法（動的計画法など）を考える必要があります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
using System; using System.Linq; class Program { static int N = 0; // 配列 A の長さ static int K = 0; static int[] A = { }; static void Main() { N = int.Parse(Console.ReadLine()); K = int.Parse(Console.ReadLine()); A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); Console.WriteLine(dfs(0, 0)); } // i 個（ A[i-1] まで）追加するしないを決めたときの 和 sum は K と等しいか？ static bool dfs(int i, int sum) { // N 個すべてについて決め終わったなら sum == K かどうかを返す if (i == N) return sum == K; // それ以外は A[i] を追加するしないで再帰呼び出しをする // もし true を返すのであれば 自分もtrueを返して終了 if(dfs(i + 1, sum)) return true; if (dfs(i + 1, sum + A[i])) return true; // そうでない場合はA[i] を追加するしないにかかわらずsum と Kにはならないのでfalseを返す return false; } } |
bit全探索
2のn乗とおりを調べるのであれば bit全探索 という方法もあります。bit全探索とは、bit演算を使って全探索をする方法です。例えば選ぶのか選ばないのかは 0 と 1 で表現できます。n個の要素を選ぶのか選ばないのかは n 桁の 2進法 の数で表現できます。これを使えば部分集合の全パターンを列挙することができます。
1 以上 9 以下の数字のみからなる文字列 S が与えられます。この文字列の中で、あなたはこれら文字と文字の間のうち、いくつかの場所に + を入れることができます。一つも入れなくてもかまいません。ただし、+ が連続してはいけません。ありうる全ての数式の値を計算し、その合計を出力してください。
入力
S
（ただしS に含まれる文字は全て 1 ～ 9 の数字で文字列の長さは1以上10以下）
各文字列中のどこに+を入れるかを考えるのであればbit全探索で全探索しましょう。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { string s = Console.ReadLine(); int len = s.Length - 1; // '+' が挿入されうる場所の個数は与えられた文字列より1少ない long ans = 0; for (int bit = 0; bit < 1 << len; bit++) { List<char> chars = s.ToList(); // ビットが立っている位の次に '+' を挿入する // 挿入することでそれ以降の位置が変わってしまうので後ろから挿入する for (int i = len - 1; i >= 0; i--) { if ((bit >> i & 1) == 1) chars.Insert(i + 1, '+'); } // いったん '+' が入った計算式をつくる string str = new string(chars.ToArray()); // '+' で分解してそれらの合計を計算する long[] vs = str.Split('+').Select(_ => long.Parse(_)).ToArray(); ans += vs.Sum(); } Console.WriteLine(ans); } } |
Bit全探索をもう一問。
AtCoder国には高橋くんを除いて N 人の国会議員と、M 個の人間関係 (x, y) が存在します。人間関係 (x, y) とは、議員 x と議員 y が知り合いであることを意味します。
高橋くんは N 人の議員から何人かを選んで派閥を作ろうと企んでいます。
派閥に含まれるすべての議員は互いに知り合いでなければなりません。
高橋くんが作成することができる最大の派閥に属する議員数を求めるプログラムを書いてください。入力
N M
x_1 y_1
x_2 y_2
x_3 y_3
…
x_M y_M
（ただし 1 ≦ N ≦ 12, 0 ≦ M ≦ N (N – 1) / 2）
これもビット全探索で 0 以上 2のN乗-1 以下の数で派閥にどの人が入っているのかを示す数をつくります。立っているふたつのビットのペア（a と b）を取得して、x_i y_i のなかに一致するものがあるかを調べます。
x_i y_i のなかに一致するものが見つからない場合は派閥を成立させるための人間関係が不足しているので派閥としてはありえないことになります。
すべての立っているビットのペア（a と b）がx_i y_i のなかに存在した場合は派閥として成立します。立っているビットの数がその派閥の人数です。これを記録しておき最大値を返します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, M; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; } int[] xs = new int[M]; int[] ys = new int[M]; for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); xs[i] = vs[0] - 1; ys[i] = vs[1] - 1; } long ans = 0; for (int bit = 0; bit < 1 << N; bit++) { bool ok = true; // 派閥のなかの人間関係を全取得する // a と ｂの人間関係はxs[i]とys[i]のペアのなかにないと派閥は構成できない for (int a = 0; a < N; a++) { for (int b = a + 1; b < N; b++) { if ((bit >> a & 1) == 1 && (bit >> b & 1) == 1) { bool find = false; for (int i = 0; i < M; i++) { if (xs[i] == a && ys[i] == b) { find = true; break; } } // xs[i]とys[i]のペアのなかに a と ｂの人間関係がみつからなかった。 // したがってこの派閥はありえない if (!find) { ok = false; break; } } } if (!ok) break; } if (ok) { int bitCount = 0; for (int i = 0; i < N; i++) { if ((bit >> i & 1) == 1) bitCount++; } ans = Math.Max(ans, bitCount); } } Console.WriteLine(ans); } } |
