AtCoder NoviStepsを埋めてみる(23) 累積和：大量の区間和を高速に求めるの続きです。今回はかっこ列です。
かっこ列問題って役に立つのか？
かっこ列問題ができたとして競技プログラミング以外で役に立つことってあるのでしょうか？ 管理人は「競技プログラミングのための競技プログラミングならやる意味なし」と考えています。かっこ列問題は数式の解析やHTML・XMLの解析、JSONの解析などで使われています。
数式であれば 3*(2+(5-1)) のように () が入れ子になっていることは普通にありますし、HTMLもタグが入れ子になっています。このようなものを解析するのであればかっこ列問題を解くスキルが必須となります。まさに「競技プログラミングは競技プログラミングのみにあらず」です。
カッコ列問題を解くときに Stack を使うことが多いのですが、Stack はランダムアクセスができないので ac-library-csharp ライブラリの Deque クラスを使うことにします。
B51 – Bracket
問題の概要
対応の取れているカッコ列 S がある。
S の何文字目と何文字目が対応しているかを、すべて出力せよ。
たとえば、(())() の場合、「1 文字目と 4 文字目」、「2 文字目と 3 文字目」、「5 文字目と 6 文字目」が対応している。
最初は超基本問題です。Stackを用意して S[i] が ‘(‘ であれば i を push し、’)’ であれば pop してその値を i とペアにして出力します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Program { static void Main() { char[] S = Console.ReadLine().ToArray(); int N = S.Length; Stack<int> stack = new Stack<int>(); for (int i = 0; i < N; i++) { if (S[i] == '(') { stack.Push(i + 1); } if (S[i] == ')') { int pop = stack.Pop(); Console.WriteLine($"{pop} {i + 1}"); } } } } |
D – Colorful Bracket Sequence
問題の概要
6 種類の文字、(, ), [, ], <, > からなる文字列 S が与えられる。
以下の操作を何回か（0 回でも良い）繰り返すことで T を空文字列にできる場合、T はカラフル括弧列と定義する。
（操作）T の（連続する）部分文字列であって、(), [], <> のいずれかであるようなものが存在するとき、そのうちの 1 つを選んで削除する。
削除された部分文字列が 削除された前後の文字列を 1 つに連結し、新たに T とする。
S はカラフル括弧列かどうか判定せよ。
Deque の末尾に S[i] を追加し、最後の 2 個が (), [], <> のいずれかであれば 2 つを取り除きます。最後に Deque が空なら S はカラフル括弧列です。
|
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 |
using AtCoder; class Program { static void Main() { char[] S = Console.ReadLine().ToArray(); int N = S.Length; Deque<char> deque = new Deque<char>(); for (int i = 0; i < N; i++) { deque.AddLast(S[i]); if (deque.Count >= 2) { bool remove = false; if (deque[deque.Count - 2] == '(' && deque[deque.Count - 1] == ')') remove = true; if (deque[deque.Count - 2] == '[' && deque[deque.Count - 1] == ']') remove = true; if (deque[deque.Count - 2] == '<' && deque[deque.Count - 1] == '>') remove = true; if (remove) { deque.PopLast(); deque.PopLast(); } } } Console.WriteLine(deque.Count == 0 ? "Yes" : "No"); } } |
D – Strange Balls
2 以上の整数が書かれた N 個のボールを細長い筒の中に落としていく。
ボールには数字が書かれていて i 回目に落とすボールには A[i] が書かれている。
筒の中で k と書かれたボールが k 個連続すると、それらのボールは消えてしまう。
i 個目のボールを筒の中に落とした後、筒の中に何個のボールがあるか求めよ。
ボールを落とすたびに A[i] が A[i] 個連続しているかどうかを調べていると TLE してしまいます。そこでランレングス圧縮をして一番上のボールとその下に何個同じ数が書かれたボールが連続しているのかがすぐにわかるようにします。
また番兵をおいて Stack が空の場合とそうでない場合の場合分けをしなくてよいようにしています。
|
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 |
class Program { class Pair { public Pair(int v, int c) { Value = v; Count = c; } public int Value = 0; public int Count = 0; } static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); Stack<Pair> stack = new Stack<Pair>(); stack.Push(new Pair(-1, 0)); // 番兵 int ans = 0; foreach (var v in A) { if (stack.Peek().Value == v) stack.Peek().Count++; else stack.Push(new Pair(v, 1)); ans++; if (stack.Peek().Value == stack.Peek().Count) ans -= stack.Pop().Count; Console.WriteLine(ans); } } } |
D – Mismatched Parentheses
英小文字および (, ) からなる長さ N の文字列 S が与えられる。
S の連続部分文字列であって、最初の文字が ( かつ 最後の文字が ) かつ 最初と最後以外に ( も ) も含まないものを自由に 1 つ選び削除するという操作を可能な限り繰り返したあとの S を出力せよ。
Deque の末尾に S[i] を追加し、それが ‘)’ であった場合は ‘(‘ が見つかるまで PopLast しつづけるという処理を繰り返せばよいです。ただし、S[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 |
using AtCoder; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); char[] S = Console.ReadLine().ToArray(); Deque<char> deq = new Deque<char>(); int start_count = 0; // Deque に格納されている '(' の個数 foreach (var ch in S) { deq.AddLast(ch); if (deq.Last == '(') start_count++; if (deq.Last == ')' && start_count > 0) { start_count--; while (true) { char pop = deq.PopLast(); if (pop == '(') break; } } } Console.WriteLine(new string(deq.ToArray())); } } |
A – 碁石ならべ
白と黒の碁石を以下のルールでテーブルの上に一列にならべる。
左から i 番目に置こうとしている碁石を S[i]、実際に左から i 番目に置かれた碁石を T[i] とする。
i が奇数の場合：
T[i] = S[i] とする。
i が偶数の場合で T[i – 1] = S[i] の場合：
T[i] = S[i] とする。
i が偶数の場合で T[i – 1] ≠ S[i] の場合：
T[i – 1] と同色で連続している石をすべて取り除き、S[i] と同じ色に置き換える。
そのあと T[i] = S[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 |
using AtCoder; class Program { class Pair { public Pair(int v, int c) { Value = v; Count = c; } public int Value = 0; public int Count = 0; } static void Main() { int N = int.Parse(Console.ReadLine()); Deque<Pair> deq = new Deque<Pair>(); deq.AddLast(new Pair(-1, 0)); // 番兵 for (int i = 0; i < N; i++) { int v = int.Parse(Console.ReadLine()); if (i % 2 == 0) { if (deq[deq.Count - 1].Value == v) deq[deq.Count - 1].Count++; else deq.AddLast(new Pair(v, 1)); } else // i が「偶数」の場合（1-based indexing なので） { if (deq[deq.Count - 1].Value == v) deq[deq.Count - 1].Count++; else { deq[deq.Count - 1].Count++; deq[deq.Count - 1].Value = v; // ブロック丸ごと色を変更する // 前のブロックと同じ色ならつなげる if (deq[deq.Count - 2].Value == deq[deq.Count - 1].Value) { deq[deq.Count - 2].Count += deq[deq.Count - 1].Count; deq.PopLast(); } } } } int ans = 0; foreach (var pair in deq) { if (pair.Value == 0) ans += pair.Count; } Console.WriteLine(ans); } } |
C – 連鎖
あるキャラクターが縦 1 列に N 個並んでいる。キャラクターの色は赤、青、黄のいずれかである。
同じ色のキャラクターが 4 つ以上連続して並ぶとそれらのキャラクターは消滅し、空間は詰められる。これによって新たに同色キャラが 4 つ以上連続して並ぶとそれらのキャラも消滅するという連鎖がおきる。
初期状態で同じ色のキャラクターが 4 つ以上連続して並んでいることはない。
プレーヤーはある位置のキャラクターを選び他の色に変更することができる。
消滅しないで残っているキャラクター数をできるだけ少なくしたい。
消滅しないで残っているキャラクター数の最小値 M を求めよ。
すべての箇所を 3 色に塗り替えた場合どうなるかを試してみるとよいです。キャラクターの総数が 10,000 であることと、実行時間制限が 10 秒であることからこれでも充分間に合います。前後のどちらの色とも違う場合はひとつも消えないことが明らかなので処理をしないことで時間短縮をしています（4228 ms → 2238 ms と改善された）。
取り除くことができるキャラを数える処理はランレングス圧縮をしたあと同じ色のキャラクターが 4 つ以上連続して並ぶ箇所がひとつだけできるので最初にその部分だけ数え、あとは Deque で同じ色のキャラクターが 4 つ以上連続するブロックができるたびに取り除く処理を繰り返します。
|
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 74 75 76 77 78 79 80 81 82 83 84 85 |
using AtCoder; class Program { class Pair { public Pair(int v, int c) { Value = v; Count = c; } public int Value = 0; public int Count = 0; } static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = new int[N + 2]; for (int i = 0; i < N; i++) A[i + 1] = (int.Parse(Console.ReadLine())); int ans = N; for (int i = 1; i <= N; i++) { int old = A[i]; for (int j = 1; j <= 3; j++) { if (A[i - 1] == j || A[i + 1] == j) { A[i] = j; ans = Math.Min(ans, F(A)); } } A[i] = old; } Console.WriteLine(ans); Deque<Pair> RunlengthEncoding(int[] arr) { Deque<Pair> pairs = new Deque<Pair>(); foreach (var v in arr) { if (pairs.Count == 0) pairs.AddLast(new Pair(v, 1)); else { if (pairs.Last.Value == v) pairs.Last.Count++; else pairs.AddLast(new Pair(v, 1)); } } return pairs; } int F(int[] arr) { Deque<Pair> pairs = new Deque<Pair>(); int res = N; foreach (var pair in RunlengthEncoding(arr)) { if (pair.Count >= 4) { res -= pair.Count; continue; } pairs.AddLast(pair); if ( pairs.Count >= 2 && pairs[pairs.Count - 1].Value == pairs[pairs.Count - 2].Value && pairs[pairs.Count - 1].Count + pairs[pairs.Count - 2].Count >= 4 ) { res -= pairs.PopLast().Count; res -= pairs.PopLast().Count; } } return res; } } } |
