AtCoder が提供しているABC（AtCoder Beginner Contest）394 D問題をC++とPythonで解いてみました。ABC394は、2025年2月22日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Colorful Bracket Sequence（Difficulty : 253）
問題の詳細は、リンク先をご覧ください。
ABC394 D問題 Colorful Bracket Sequence
スタックを使って文字列を削除していきます。AtCoder Problems による Difficulty は 253 でした。
解答案
C++ プログラム例（ABC394D）
3種類の括弧、すなわち ()、[]、<> を再帰的に削除した結果、空文字列になるかを確認します。文字列をスタックと考えて処理しました。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin >> s;
vector<char> st;
for (int i = 0; i < (int)s.length(); ++i) {
if (s[i] == ')') {
if ((st.size() > 0) && (st.back() == '(')) {
st.pop_back();
} else {
st.push_back(s[i]);
}
} else if (s[i] == ']') {
if ((st.size() > 0) && (st.back() == '[')) {
st.pop_back();
} else {
st.push_back(s[i]);
}
} else if (s[i] == '>') {
if ((st.size() > 0) && (st.back() == '<')) {
st.pop_back();
} else {
st.push_back(s[i]);
}
} else {
st.push_back(s[i]);
}
}
if (st.size() == 0) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC394D）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 394 D"""
s = input()
st = []
for ch in s:
if ch == ')':
if len(st) > 0 and st[-1] == '(':
st.pop()
else:
st.append(ch)
elif ch == ']':
if len(st) > 0 and st[-1] == '[':
st.pop()
else:
st.append(ch)
elif ch == '>':
if len(st) > 0 and st[-1] == '<':
st.pop()
else:
st.append(ch)
else:
st.append(ch)
print("Yes" if len(st) == 0 else "No")こちらも「AC」と判定されました。
最後に
ABC064D問題（解説記事）は少し難しいですが、似たテクニックを使います。
引き続き ABC の問題を紹介していきます。
