AtCoder

ABC307 D問題(Mismatched Parentheses)を解く

AtCoder_ABC307_D

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問題は、スタックを使う発想が思い浮かべば、プログラムもそれほど複雑ではありませんでした。難易度を見極めて、適切な順番で解いていければと思います。

ABC307 について、引き続き問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA