ABC064 D問題（Insertion）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）064 D問題をC++で解いてみました。ABC064は、2017年6月10日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 Insertion（Difficulty : 969）

問題の詳細は、リンク先をご覧ください。

ABC064 D問題 Insertion

スタックを使って文字列を最小化します。AtCoder Problems による Difficulty は 969 でした。

解答案

与えられた文字列内の ‘(‘ と、それ以降の位置にある ‘)’ を組み合わせて消去します。この操作で残った ‘)’ の個数だけ文字列の左に ‘(‘ を、残った ‘(‘ の個数だけ文字列の右に ‘)’ を追加すれば、解答となります。

C++ プログラム例（ABC064D）

上記の考察に従い、正規表現で記せば “)*(*” の形に文字列を変形してから、左右に文字を加えました。

以下が、C++プログラムです。

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin >> n;
	string s;
	cin >> s;

	vector<int> st;
	for (int i = 0; i < n; ++i) {
		if (s[i] == ')') {
			if ((st.size() > 0) && (st.back() == '(')) {
				st.pop_back();
			} else {
				st.push_back(s[i]);
			}
		} else {
			st.push_back(s[i]);
		}
	}

	int lp = 0;
	int rp = 0;
	for (auto e : st) {
		if (e == '(') {
			++lp;
		} else {
			++rp;
		}
	}

	cout << string(rp, '(') + s + string(lp, ')') << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

最後に

この当時は、この問題も緑レートの問題でした。

引き続き ABC の問題を紹介していきます。