@aizawa_0138

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

ABC 428のC問題について

解決したいこと

昨日行われたAtcoder Beginner Contest 428のC問題で何を見落としているのかが分からなかったので、説明して頂きたいです。まだプログラミングを始めて一か月の初心者なのでコードはとても汚いですが、教えて頂けると嬉しいです。

問題のリンク:https://atcoder.jp/contests/abc428/tasks/abc428_c
提出したコード:https://atcoder.jp/contests/abc428/submissions/70263568

発生している問題・エラー

AtCoderにて行った入力がSampleでACできたのですが、それ以外のテストケースでAC x 7とWA x 11になりました。

該当するソースコード

q = int(input())
lst = []
count = 0
scary = []

for i in range(q):
    query = input().split()
    if query[0] == "1":
        c = query[1]
        if c == "(":
            count += 1
        elif c == ")":
            if count <= 0:
                scary.append(i + 1)
            count -= 1
        lst.append(c)
        print("Yes" if count == 0 and len(scary) == 0 else "No")
    if query[0] == "2":
        last = lst[len(lst) - 1]
        if last == "(":
            count -= 1
        else:
            count += 1
        if len(scary) != 0 and scary[len(scary) - 1] == len(lst):
            scary.pop()
        lst.pop()
        print("Yes" if count == 0 and len(scary) == 0 else "No")

どう考えてコードを組んだか

開いている括弧と閉じている括弧の数が同じかつ、開いていないのに閉じている括弧が存在しないことがYesを出力するための条件だと思いました。

1. 括弧数について

この条件をコードに落とすために"1"が入力されたときに条件分岐で"("が入力されたときはカウントを1足して、")"が入力されたときはカウントを1引いて、入力された括弧の形をlstに格納します。"2"が入力されたときはlstの最後の括弧の形が"("ならカウントを1引いて、")"ならカウントを1足して、lstの最後の括弧を除去します。カウントが0のとき、(開いている括弧と閉じている括弧が同じのとき)にYesを出力するようにしました。

2. 開いていないのに閉じている括弧の存在について

この条件をコードに落とすために、開いていないのに閉じた場合はscaryという別のリストにその括弧がlstの何番目にあるのかを格納します。"2"が入力された場合、lstの末尾から弾いていくので、開いていないのに閉じている括弧が何番目にあるのかは変わらないと思いました。もし"2"が入力され、scaryの末尾とlstの長さが一致しているのなら、開いていないのに閉じている括弧を弾くのと同義だと思いました。scaryの長さが0のとき、(開いていないのに閉じている括弧が存在しないとき)にYesを出力するようにしました。

これらの二つの条件を組み合わせて実装しようとしたのですが、上手くいきませんでした。その原因を教えて頂けませんか?拙い説明で申し訳ないですが、よろしくお願いします。

0 likes

1Answer

この条件をコードに落とすために、開いていないのに閉じた場合はscaryという別のリストにその括弧がlstの何番目にあるのかを格納します。

こちらが正しく実装されていません。scary.append(i + 1)だと、その括弧が何番目のクエリで追加されたかを格納していることになります。

こちらの入力例の処理を追えば、両者の違いが分かると思います。

4
1 )
2
1 )
2
1Like

Comments

  1. @aizawa_0138

    Questioner

    回答ありがとうございます!
    actorbugさんの回答を受けて、scary.append(len(lst) + 1) に直したらACすることが出来ました!ありがとうございます!!

  2. 解決済みと思われるので、当Q&Aをクローズすることをオススメします。
    クローズされていないと、まだ何らか回答を期待しているかと思われますので。

  3. @aizawa_0138

    Questioner

    アドバイスありがとうございます!
    クローズさせていただきます!

Your answer might help someone💌