A[j] ≧ A[i] である最大のjを求める
A[j] ≧ A[i] である最大の j (ただし j ＜ i)を求めるのであれば簡単にできます。
|
1 2 3 4 5 6 7 8 9 10 |
int ans = -1; for (int j = i - 1; j >= 0; j--) { if (A[j] >= A[i]) { ans = j; break; } } Console.WriteLine($"i: {i}, j: {ans}"); |
しかしすべてのiについてjを求めなければならないときに以下のようにするのは効率が悪すぎます。時間計算量は配列の長さを N とすると O(N^2) になってしまいます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
for (int i = 0; i < A.Length; i++) { int ans = -1; for (int j = i - 1; j >= 0; j--) { if (A[j] >= A[i]) { ans = j; break; } } Console.WriteLine($"i: {i}, j: {ans}"); } |
スタックを使うと O(N) でできます。スタックに添字と値をペアにしたものを格納していくのですが、Pushするまえに小さな値があればすべてPopしてしまいます。それによってスタックが空になってしまえば解なし（-1）、空でない場合はPeekで得られる添字が解となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Stack<(int, int)> stack = new Stack<(int, int)>(); for (int i = 0; i < A.Length; i++) { while (stack.Count > 0 && stack.Peek().Item2 < A[i]) stack.Pop(); if (stack.Count == 0) Console.WriteLine($"i: {i}, j: {-1}"); else Console.WriteLine($"i: {i}, j: {stack.Peek().Item1}"); stack.Push((i, A[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 |
// すべての i について A[j] ≧ or ＞ A[i] である最大の j (ただし j ＜ i)を求める int[] GetLastIndexesLarger(int[] arr, bool equal) { int n = arr.Length; int[] rets = new int[n]; Stack<(int, int)> stack = new Stack<(int, int)>(); for (int i = 0; i < n; i++) { while (stack.Count > 0) { if (equal ? stack.Peek().Item2 < arr[i] : stack.Peek().Item2 <= arr[i]) stack.Pop(); else break; } if (stack.Count == 0) rets[i] = -1; else rets[i] = stack.Peek().Item1; stack.Push((i, arr[i])); } return rets; } // すべての i について A[j] ≧ or ＞ A[i] である最小の j (ただし j ＞ i)を求める int[] GetFirstIndexesLarger(int[] arr, bool equal) { int n = arr.Length; int[] rets = new int[n]; Stack<(int, int)> stack = new Stack<(int, int)>(); for (int i = n - 1; i >= 0; i--) { while (stack.Count > 0) { if (equal ? stack.Peek().Item2 < arr[i] : stack.Peek().Item2 <= arr[i]) stack.Pop(); else break; } if (stack.Count == 0) rets[i] = n; else rets[i] = stack.Peek().Item1; stack.Push((i, arr[i])); } return rets; } |
本当に幸せになれるのでしょうか？
D – 登山家
これはすべての i について A[j] ＞ A[i] である最小の j1 と最大の j2 を求めてその間の長さ（i, j1, j2は含めない）を求めればよいという問題です。
上で定義したメソッドを使えば解けそうです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Program { static void Main() { // 上とまったく同じなので定義は省略 // int[] GetLastIndexesLarger(int[] arr, bool equal) // int[] GetFirstIndexesLarger(int[] arr, bool equal) int N = int.Parse(Console.ReadLine()); int[] A = new int[N]; for (int i = 0; i < N; i++) A[i] = int.Parse(Console.ReadLine()); int[] lefts = GetLastIndexesLarger(A, false); int[] rights = GetFirstIndexesLarger(A, false); for (int i = 0; i < N; i++) { int ans = rights[i] - lefts[i] - 2; // 境界とiそれ自身を除く長さ Console.WriteLine(ans); } } } |
C – 行列のできるドーナツ屋
ちょっと考察が必要ですが、これも上で定義したメソッドを使うと解ける問題です。
これは人を三色の棒で表現したものですが、青い人よりも右側にある青い人よりも高い人を探してみると赤い人が見つかります。
人の高さの配列を A、青い人がいる位置を b、赤い人がいる位置を r と置きます。このとき、b と r の間には A[b] を超えるものが存在しないことに気づきます。ここから b + 1 番目から r 番目までの人は青い人を見ることができることがわかります。
そこで解を格納する配列 B を定義して b + 1 番目から r 番目まで 1 を加算します。先頭から最後尾まで i番目が青い人だったらどうなるかを考えれば解を得ることができます。
ただし広い区間に1を追加する処理をそのままやろうとすると時間がかかるので、「imos法」を使います。これは区間[a, b]にvを追加するという処理を繰り返す場合、imos[a] += v, imos[b + 1] -= v とし、最後にimosの累積和（先頭から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 |
class Program { static void Main() { // 上とまったく同じなので定義は省略 // int[] GetFirstIndexesLarger(int[] arr, bool equal) int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] rights = GetFirstIndexesLarger(A, false); int[] imos = new int[N]; for (int i = 0; i < N; i++) { int r = rights[i]; // 区間[i + 1, r] は i が見えるので [i + 1, r]に1を足す // imos法だと imos[i + 1]++、imos[r + 1]--。 if (i + 1 < N) imos[i + 1]++; if(r + 1 < N) imos[r + 1]--; } // imosの累積和を計算する。これが答えとなる for(int i = 0; i < N - 1; i++) imos[i + 1] += imos[i]; foreach (int v in imos) Console.WriteLine(v); } } |
