はじめに
本記事はPythonでAtcoderにチャレンジしているけど、Pythonはコード例がないため解説がわかりにくい！と感じている方を対象としています。
私自身大してレートも高くないので、不備等あるかもしれませんがご了承くださいm(_ _)m
ユニークビジョンプログラミングコンテスト2022冬 D問題
問題のURLはこちらです。ユニークビジョンプログラミングコンテスト2022冬 D問題
使うデータ構造
スタックを使っていきます。
スタックとはなんぞや？って方はこちらの記事を見て見てください。非常にわかりやすく解説してくれています。
また、今回私はlistを使ってスタックを実装しましたが、collections.dequeを使用した方が計算速度は早いそうです。こちらの記事で検証されていました。
初学者の方はcollections.dequeについても併せて勉強すると良いかもしれません。
考え方
ざっくりとしたコンセプトを、以下のフローチャートに示します。
(パワポでささっと作ったので見にくくてすいません・・・・・・)
また、これだけではわかりにくいと思いますので、S=(ab(c)ab) とした時のスタック内部の状態を図にしました。(これでもわかりにくかったらすいません・・・・・)
あとはこれを実装していきます。
実装例
#標準入力
s = input()
#YesかNoかを管理するフラグ
booler = True
#スタックの高さを管理する値
deep_count = 0
"""
スタックの作成。
初期状態で空のリストを追加していますが、あまり気にしないでください。
"""
stack = list()
stack.append(list())
"""
各アルファベットをキーとした辞書型の配列「al_dict」を作成。
これによって現在箱に各アルファベットが箱に入っているかを管理
(Trueなら箱にその文字が入っている。Falseなら入っていない。)
"""
al_dict = dict()
for i in range(26):
al_dict[chr(ord("a")+i)] = False
#sの各文字について見ていく。なお、iは文字の位置を示すインデックスのため注意。
for i in range(len(s)) :
#現在見ている位置の文字「moji」を取得。
moji = s[i]
if moji == "(":
"""
mojiが「(」の場合、新たなスタックが追加される。
スタックが追加されたため、deep_countを+1する。
"""
stack.append(list())
deep_count += 1
elif moji == ")":
"""
mojiが「)」の場合、スタックの最も上にある配列を取り出す。
以降 この配列を「sweep」と名付けます。
"""
sweep = stack[deep_count]
"""
sweep内に格納されたアルファベットたちをキーとするal_dict[key]の値を
Falseに変更する。
"""
for j in sweep :
al_dict[j] = False
"""
上記の処理によって箱から取り出す処理が完了したので、stackからsweepを削除する。
また、これによってstackの高さも低くなったため、deep_countを-1する。
"""
stack.pop(-1)
deep_count -= 1
else :
if al_dict[moji] :
booler = False
break
else :
stack[deep_count].append(moji)
al_dict[moji] = True
if booler :
print("Yes")
else :
print("No")
計算量に関する記載
今問題の制約は 1<=|S|<= 3×10^5となっています。
私のコードでは一部二重ループとなっており、一見すると計算量はO(N^2)となりTLEになりそうですが、sweepをループさせる場合最大でも26回で済みます。(アルファベットの数は26個で、これ以上の値が各sweep内に格納されることはありません。)
sweep自体も問題文の条件から、大した量生成されないので、本問題では二重ループでも問題なく計算が終了します。