AtCoder が提供しているABC（AtCoder Beginner Contest）328 のD問題をC++とPythonで解いてみました。ABC328は、2023年11月11日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Take ABC（Difficulty : 555）
問題はリンク先をご覧ください。
スタックを使って文字列を処理します。AtCoder Problems による Difficulty は 555 でした。
解答案
スタックを使います。
- 空のスタックを用意する。文字列の先頭から文字を処理していく。
- 文字が ’C’ の場合
- スタックの先頭の文字が ’B’ の場合
- スタックをpopする。
- この時点でのスタックの先頭の文字が ’A’ の場合
- スタックをpopする。この操作により “ABC” を削除したことになる。次の文字を処理する。
- この時点でのスタックの先頭の文字が ’A’ ではない場合
- すでにpopした文字 ‘B’ をpushする。
- スタックの先頭の文字が ’B’ の場合
- 文字をpushする。
- 文字が ’C’ の場合
C++ プログラム例（ABC328D）
上記の操作をプログラムにします。Vector コンテナをスタックとして使いました。文字列をすべて走査した時点でスタックに残っている文字を Vector コンテナの先頭から出力します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin >> s;
int n = s.length();
vector<char> st;
for (int i = 0; i < n; ++i) {
if (s[i] == 'C') {
if ((!st.empty())&&(st.back() == 'B')) {
st.pop_back();
if ((!st.empty())&&(st.back() == 'A')) {
st.pop_back();
continue;
} else {
st.push_back('B');
}
}
}
st.push_back(s[i]);
}
string result = "";
for (auto e : st) {
result += e;
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC328D）
Python 版も基本的な考え方は同じです。リストをスタックとして使います。以下となります。
"""AtCoder Beginner Contest 328 D"""
s = input()
stack = []
for _, ch in enumerate(s):
if ch == 'C':
if len(stack) != 0 and stack[-1] == 'B':
stack.pop()
if len(stack) != 0 and stack[-1] == 'A':
stack.pop()
continue
else:
stack.append('B')
stack.append(ch)
result = ""
for _, ch in enumerate(stack):
result += ch
print(result)こちらも「AC」と判定されました。
最後に
スタックを使って処理することにより解くことができました。基本的なデータ構造であるスタック/キュー/優先度付きキュー/連想配列について、慣れてきた気がします。
引き続き ABC の問題を紹介していきます。
