二分探索法を活用することで全探索をするよりも計算量を減らすことができます。
全探索でもできるが・・・
赤・青・白の 3 枚のカードがあります。
太郎君は、それぞれのカードに 1 以上 N 以下の整数を書かなければなりません。3 枚のカードの合計を K にするような書き方は何通りありますか。ただし 1 ≦ N ≦ 3000, 3 ≦ K ≦ 9000
一見するとこれでよさそうですが、N が 3000のような大きな値になると制限時間以内には終わりません。
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, K; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; K = vs[1]; } int ans = 0; for (int a = 1; a <= N; a++) { for (int b = 1; b <= N; b++) { for (int c = 1; c <= N; c++) { if (a + b + c == K) ans++; } } } Console.WriteLine(ans); } } |
a, b, c は a + b + c = K になるような値なので、a と b が決まると c もひとつの値になります。そこで3重ループではなく2重ループで解を求めることができます。
注意点としては a, b の値によっては c の値が不適切な値になる場合があるので注意することです。この場合は 1 以上 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 |
class Program { static void Main() { int N, K; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; K = vs[1]; } int ans = 0; for (int a = 1; a <= N; a++) { for (int b = 1; b <= N; b++) { int c = K - a - b; // a, b の値によっては c の値が不適切な値になる場合があるので注意する if (c >= 1 && c <= N) ans++; } } Console.WriteLine(ans); } } |
全探索ではなく二分探索法で計算量を減らす
このように範囲が狭い場合はよいのですが、次の問題はどうでしょうか？
A・B・C・D の 4 つの箱があります。各箱には以下の N 枚のカードが入っています。
箱 A には整数 A1, A2, …… An
箱 B には整数 B1, B2, …… Bn
箱 C には整数 C1, C2, …… Cn
箱 D には整数 D1, D2, …… Dnあなたはそれぞれの箱から 1 枚ずつカードを取り出します。取り出した 4 枚のカードに書かれた整数の合計が
K となる可能性はあるか、判定してください。ただし 1 ≦ N ≦ 1000, 1 ≦ K ≦ 10の8乗
N が最大で 1000 なので4重ループで全探索をしていては制限時間以内には終わりません。
そこで二分探索法で計算量を減らすことを考えます。AとB、CとDでとりあえずAB, CDのペアをつくりこれらをソートします。そして二分探索法でCDのなかからABの各要素に対応するものがないか調べるのです。
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, K; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; K = vs[1]; } int[] As = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] Bs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] Cs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] Ds = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] ABs = new int[N * N]; int[] CDs = new int[N * N]; for (int a = 0; a < N; a++) { for (int b = 0; b < N; b++) ABs[a * N + b] = As[a] + Bs[b]; } for (int c = 0; c < N; c++) { for (int d = 0; d < N; d++) CDs[c * N + d] = Cs[c] + Ds[d]; } ABs = ABs.OrderBy(_ => _).ToArray(); CDs = CDs.OrderBy(_ => _).ToArray(); bool find = false; foreach (int i in ABs) { int target = K - i; int left = 0; int right = CDs.Length; while (right - left > 1) { int mid = (left + right) / 2; if (CDs[mid] == target) { find = true; break; } if (CDs[mid] < target) left = mid; if (CDs[mid] > target) right = mid; } if (find) break; } if (find) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } |
