ひとりで勝手にはじめた蟻本読書会 反転 (ライツアウト) 蟻本読書会 の続きです。
全探索では全通り直接的に探索を行うので、対象の数が増えると計算量は指数関数的に増えてしまいます。半分全列挙とは、半分ずつのグループに分け、全探索を高速化するテクニックです。
C – 無駄なものが嫌いな人
私は無駄なものが嫌いなので、無駄なことを言わずに言いたいことだけ言おう。
世の中にはナップサック問題というものがあり、決まった大きさのナップサックにできるだけ価値が高くなるよう品物を詰めることを考えるらしいが、そんなことを考えても無駄である。
価値がいくら高くなったところで、ナップサックに無駄なスペースができてしまうのは許せない。私は無駄なものが嫌いなのだ。
導入部分はなかなかおもしろいです。では問題の本題に入りましょう。
今ここに大きさ X のナップサックと N 個の品物がある。i 番目の品物の大きさは w_i である。N 個の品物から、大きさの総和がちょうど X となる選び方が何通りあるだろうか？
入力されるデータ
N X
w_1
w_2
:
w_N（ただし、1 ≦ N ≦ 32, 1 ≦ X ≦ 10^9
1 ≦ w_i ≦ 5×10^7 ）
品物それぞれについていれるいれないで全探索をしようとすると N が 最大で 32 であることから全部で 2^32 とおりの計算をする必要があります。これでは制限時間内に間に合いません。
そこで半分ずつ考えます。これならそれぞれのグループの組み合わせは 2^16 とおりに減らせます。あとは一方のグループのなかから総和がちょうど X になるものがあるかを探せばよいのです。
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, X; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; X = vs[1]; } // 入力を半分ずつにわける int half = N / 2; List<int> A = new List<int>(); List<int> B = new List<int>(); for (int i = 0; i < N; i++) { if(i < half) A.Add(int.Parse(Console.ReadLine())); else B.Add(int.Parse(Console.ReadLine())); } // 前半部分のそれぞれを選ぶ選ばないで半分全列挙して合計をリストに格納する List<long> WA = new List<long>(); for (int b = 0; b < 1 << A.Count; b++) { long w = 0; for (int i = 0; i < A.Count; i++) { if (((b >> i) & 1) == 1) w += A[i]; } WA.Add(w); } // 後半部分のそれぞれを選ぶ選ばないで半分全列挙して合計を辞書に格納する // 前半部分と足して X になるものをこのなかから探すのだが、高速で検索できるように辞書を使う Dictionary<long, long> dic = new Dictionary<long, long>(); for (int b = 0; b < 1 << B.Count; b++) { long w = 0; for (int i = 0; i < B.Count; i++) { if (((b >> i) & 1) == 1) w += B[i]; } if(!dic.ContainsKey(w)) dic.Add(w, 1); else dic[w]++; } long ans = 0; foreach (long a in WA) { // a と足すと X になる数（X - a）を探す if (dic.ContainsKey(X - a)) ans += dic[X - a]; } Console.WriteLine(ans); } } |
C – String Coloring
長さ 2N の英小文字のみからなる文字列 S が与えられます。
S の各文字を赤色か青色かに塗り分ける方法は 2 の 2N 乗 通りありますが、このうち「赤色に塗られた文字を左から右に読んだ文字列と青色に塗られた文字を右から左に読んだ文字列が一致する」という条件を満たす塗り分け方は何通りあるでしょうか？
入力されるデータ
N
S
（ただし、1 ≦ N ≦ 18, S は英小文字のみからなる文字列）
文字列 S の長さは偶数です。これもふたつに分けて半分にずつ考えるとなにか見えてくるかもしれません。
「赤色に塗られた文字を左から右に読んだ文字列と、青色に塗られた文字を右から左に読んだ文字列が一致する」ためには赤と青の文字は同じ数でなければなりません。前半部分の赤の文字数を X とすると前半の青の文字数は N – X となりますが、赤と青の文字は同じ数でなければならないとすると、後半部分の赤の文字数は N – X であり、青の文字数は X となります。
前半部分の赤の文字数と後半部分の青の文字数は同じ
前半部分の赤の文字列を反転したものと後半部分の青の文字列は同じ
前半部分の青の文字列を反転したものと後半部分の赤の文字列は同じ
前半部分の赤の文字列と青の文字列を半分全列挙します。そして同様に後半部分の赤の文字列と青の文字列も半分全列挙するのですが、生成した文字列は反転してから辞書に格納します。キーは前半部分の赤の文字列と青の文字列を “-” でつないだ文字列を用いています。そのあとリスト内に格納された文字列を取り出して、条件にあった文字列が辞書のなかにないか調べています。
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); char[] chars = Console.ReadLine().ToArray(); List<string> R1 = new List<string>(); List<string> B1 = new List<string>(); for (int b = 0; b < 1 << N; b++) { List<char> cs1 = new List<char>(); List<char> cs2 = new List<char>(); for (int i = 0; i < N; i++) { if (((b >> i) & 1) == 1) cs1.Add(chars[i]); else cs2.Add(chars[i]); } R1.Add(new string(cs1.ToArray())); B1.Add(new string(cs2.ToArray())); } Dictionary<string, long> dic = new Dictionary<string, long>(); for (int b = 0; b < 1 << N; b++) { List<char> cs1 = new List<char>(); List<char> cs2 = new List<char>(); for (int i = 0; i < N; i++) { if (((b >> i) & 1) == 1) cs1.Add(chars[i + N]); else cs2.Add(chars[i + N]); } cs1.Reverse(); cs2.Reverse(); string red = new string(cs1.ToArray()); string blue = new string(cs2.ToArray()); if (!dic.ContainsKey($"{red}-{blue}")) dic.Add($"{red}-{blue}", 1); else dic[$"{red}-{blue}"]++; } long ans = 0; for (int i = 0; i < R1.Count; i++) { string key = $"{B1[i]}-{R1[i]}"; if (dic.ContainsKey(key)) ans += dic[key]; } Console.WriteLine(ans); } } |
