AtCoder が提供しているABC（AtCoder Beginner Contest）307 のD問題をC++とPythonで解いてみました。ABC307は、2023年6月24日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Mismatched Parentheses（Difficulty : 666）
問題はリンク先をご覧ください。
ABC307 D問題 Mismatched Parentheses
スタックを使って文字列を処理する問題です。AtCoder Problems による Difficulty は 666 でした。
解答案
文字列をスタックで処理していきます。右カッコ ‘)’ を見つけたときの処理は、左カッコ ‘(‘ が既にあるかないかで処理が変わります。
- 左カッコ ‘(‘ がある場合：右カッコから左カッコまでの文字列を削除する。
- 左カッコ ‘(‘ がない場合：そのまま右カッコをスタックに積む。
C++ プログラム例（ABC307D）
スタックを vector コンテナで実装しました。左カッコの数を変数 left_count で管理します。この変数は左カッコにより増やし、右カッコにより減らします。
文字列 S を使いながら char 配列 result を上記の考察にしたがい更新します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
string s;
cin >> s;
vector<char> result;
int left_count = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '(') {
++left_count;
result.push_back(s[i]);
} else if (s[i] == ')') {
if (left_count > 0) {
while (true) {
char ch;
ch = result.back();
result.pop_back();
if (ch == '(') {
--left_count;
break;
}
}
} else {
result.push_back(s[i]);
}
} else {
result.push_back(s[i]);
}
}
for (int i = 0; i < result.size(); ++i) {
cout << result[i];
}
cout << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC307D）
Python 版では、リストを使ってスタックを実装しました。pop で値が取れるため、条件文でそのまま判断しています（14行目）。
"""AtCoder Beginner Contest 307 D"""
n = int(input())
s = input()
result = []
left_count = 0
for i, ch in enumerate(s):
if ch == '(':
left_count += 1
result.append(ch)
elif ch == ')':
if left_count > 0:
while True:
if result.pop() == '(':
left_count -= 1
break
else:
result.append(ch)
else:
result.append(ch)
print(*result, sep='')こちらも「AC」と判定されました。
最後に
C問題の難易度が高く（実装が重く）、D問題と Difficulty が逆転していました。D問題は、スタックを使う発想が思い浮かべば、プログラムもそれほど複雑ではありませんでした。難易度を見極めて、適切な順番で解いていければと思います。
引き続き ABC の問題を紹介していきます。
