C++の練習を兼ねて, AtCoder Beginner Contest 064 の 問題D（Insertion) を解いてみた.
■感想.
1. 左括弧 ‘)’ を軸に考えてみたところ, 何とか解答できた.
2. 標準ライブラリ std::deque を使う練習が出来たと思われる.
本家のサイトAtCoder Beginner Contest 064 解説をご覧下さい.
■C++版プログラム(AC版).
|
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 |
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) int main() { // 1. 入力情報取得. int N; string S; cin >> N; cin >> S; // 2. 正しい括弧列を構成. // 文字列S を左から確認して, // '(' なら, 左括弧のカウンターを +1 する. // ')' なら, 左括弧のカウンターを -1 するか, 右括弧を追加する. // deque<char> dq; int l = 0; // '('カウンター(※左括弧が, どのくらい出現し過ぎているかチェック) FOR(i, 0, S.size()) { char c = S[i]; dq.push_back(c); if(c == '(') l++; if(c == ')') { if(l == 0) dq.push_front('('); else l--; } } // 3. 出力文字列を作成. // l が 0 より大きい場合に, 注意が必要. string ans; for(auto &c : dq) ans += c; FOR(i, 0, l) ans += ')'; // 4. 出力 ～ 後処理. cout << ans << endl; return 0; } |
■参照サイト
AtCoder Beginner Contest 064