int型の配列内に指定された整数が存在するかを調べる問題。配列はすでにソートされています。配列のサイズは最大で200,000です。
なにも考えずに以下の方法では時間がかかりすぎであり不合格。
|
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 |
using System; using System.Linq; class Program { static void Main() { int n = int.Parse(Console.ReadLine()); int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); // 配列をつくる。ここまでは問題ない。 int q = int.Parse(Console.ReadLine()); int[] values = new int[q]; for (int i = 0; i < q; i++) values[i] = int.Parse(Console.ReadLine()); // 問題はここから。nとqの最大値は200,000。これでは時間がかかりすぎる for (int i = 0; i < q; i++) { int value = values[i]; bool isYes = false; for (int k = 0; k < n; k++) { if (vs[k] == value) { isYes = true; break; } } if(isYes) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } } |
ではこれはどうか？ ソートされているのだから配列から取り出した値が探している値より大きくなった段階で「存在しない」と判断します。
しかし、たいした解決策にはなっていないらしくダメなものはダメ。
|
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 |
using System; using System.Linq; class Program { static void Main() { int n = int.Parse(Console.ReadLine()); int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int q = int.Parse(Console.ReadLine()); int[] values = new int[q]; for (int i = 0; i < q; i++) values[i] = int.Parse(Console.ReadLine()); for (int i = 0; i < q; i++) { int value = values[i]; bool isYes = false; for (int k = 0; k < n; k++) { if (vs[k] == value) { isYes = true; break; } // ソートされているのだからvs[k] > valueとなった段階で探すのは時間の無駄である if (vs[k] > value) break; } if (isYes) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } } |
正しいやり方はこれ。対象とする探索範囲の中央の値と探索したい値を比較します。これで探索範囲を半分に減らせます。これを繰り返せば無駄な探索をする必要がなくなります。これならnとqが200000の場合でもわずか0.74 秒で完了します。なにも考えずに最初からループを回して探すのとは大きな違いです。
|
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 |
using System; using System.Linq; class Program { // ソート済みの数列 vs に 値 target が含まれているなら true を、含まれていないなら no を返す static bool binary_search(int[] vs, int n, int target) { // 探索範囲 [left, right] int left = 0; int right = n - 1; // 探索範囲を狭めていく while (left <= right) { // 探索範囲の中央 int centerIndex = (left + right) / 2; int centerValue = vs[centerIndex]; if (centerValue == target) return true; else if (centerValue < target) left = centerIndex + 1; else right = centerIndex - 1; } return false; } static void Main() { int n = int.Parse(Console.ReadLine()); int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int q = int.Parse(Console.ReadLine()); int[] values = new int[q]; for (int i = 0; i < q; i++) values[i] = int.Parse(Console.ReadLine()); for (int i = 0; i < q; i++) { if (binary_search(vs, n, values[i])) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } } |
これはソートすれば解決しそう。n、qの最大値は200000なので実際に200000個の乱数を生成してソートにかかる時間を計測してみます。
|
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 |
using System; using System.Linq; class Program { static void test() { var sw = new System.Diagnostics.Stopwatch(); Random random = new Random(); int[] vs = new int[200000]; for (int i = 0; i < 200000; i++) { vs[i] = random.Next(1000000); } sw.Start(); vs = vs.OrderByDescending(x => x).ToArray(); sw.Stop(); Console.WriteLine($" {sw.ElapsedMilliseconds}ミリ秒"); } static void Main() { test(); } } |
結果は88ミリ秒。あとは上記と同じ方法でよいのですが、配列内にその値があるかどうかはわかりません。境界線を知る必要があります。そこで配列のなかにある値以上のものの個数を求めるGetCount1メソッドを定義します。
|
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 |
using System; using System.Linq; class Program { static void Main() { int n = int.Parse(Console.ReadLine()); int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int q = int.Parse(Console.ReadLine()); int[] values = new int[q]; for (int i = 0; i < q; i++) values[i] = int.Parse(Console.ReadLine()); // 昇順にソートする vs = vs.OrderBy(x => x).ToArray(); for (int i = 0; i < q; i++) Console.WriteLine(GetCount1(vs, n, values[i])); } // vsのなかにあるtarget以上のものの個数を求める static int GetCount1(int[] vs, int n, int target) { // vs は昇順にソートされている // 探索範囲 [left, right] int left = 0; int right = n; // 探索範囲を狭めていく while (left < right) { // 探索範囲の中央 int centerIndex = (left + right) / 2; int centerValue = vs[centerIndex]; if (centerValue < target) left = centerIndex + 1; else right = centerIndex; } // target以上の個数を知りたいので全体からrightを引く return n - right; } } |
今度は与えられた数より大きい要素の数を求める問題です。「以上」ではなく「より大きい」なので同じ数だとカウントしません。
一箇所を変えるだけなのですが、解説では「3つめの引数に1大きな値を渡すことでも問題を解くことができる」とのこと。
|
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 |
using System; using System.Linq; class Program { static void Main() { int n = int.Parse(Console.ReadLine()); int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int q = int.Parse(Console.ReadLine()); int[] values = new int[q]; for (int i = 0; i < q; i++) values[i] = int.Parse(Console.ReadLine()); vs = vs.OrderBy(x => x).ToArray(); for (int i = 0; i < q; i++) Console.WriteLine(GetCount2(vs, n, values[i])); // Console.WriteLine(GetCount1(vs, n, values[i] + 1));のほうが簡単かも } // vsのなかにあるtargetより大きいものの個数を求める static int GetCount2(int[] vs, int n, int target) { // vs は昇順にソートされている // 探索範囲 [left, right] int left = 0; int right = n; // 探索範囲を狭めていく while (left < right) { // 探索範囲の中央 int centerIndex = (left + right) / 2; int centerValue = vs[centerIndex]; if (centerValue <= target) // 変更箇所 < を <= に変更した left = centerIndex + 1; else right = centerIndex; } return n - right; } } |
いよいよラスボスです。配列内の整数のうち、a 以上 b 以下の個数を求めよという問題です。
これまで同様に数列をソート、a 以上の値が最初に現れる位置から b より大きい値が最初に現れる位置を引けば出力すれば、a 以上 b 以下の個数を取得できます。
|
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 |
using System; using System.Linq; class Program { static void Main() { int n = int.Parse(Console.ReadLine()); int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int q = int.Parse(Console.ReadLine()); int[] mins = new int[q]; int[] maxs = new int[q]; for (int i = 0; i < q; i++) { int[] vs1 = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); mins[i] = vs1[0]; maxs[i] = vs1[1]; } vs = vs.OrderBy(x => x).ToArray(); for (int i = 0; i < q; i++) { // vsのなかにあるtarget以上のもので最小のindexを求める int minIndex = GetIndex(vs, n, mins[i]); // vsのなかにあるtargetより大きなもので最小のindexを求めるためにmaxs[i]に1加えたものを渡す int maxIndex = GetIndex(vs, n, maxs[i] + 1); Console.WriteLine(maxIndex - minIndex); } } // vsのなかにあるtarget以上のもので最小のindexを求める static int GetIndex(int[] vs, int n, int target) { int left = 0; int right = n; while (left < right) { int centerIndex = (left + right) / 2; int centerValue = vs[centerIndex]; if (centerValue < target) left = centerIndex + 1; else right = centerIndex; } return right; } } |
