問題の要約
空文字列であるsにQ個のクエリを施し、その各クエリの直後にそれぞれの()が対応する「良い括弧列」であるかを判定する。
クエリは800000あるので、「良い括弧列であるか」の判定をO(1)程度でできないと3秒に間に合わない。
解説
クエリを処理する流れはデータ型的に言うとStack(後入先出)様のもの。
1のクエリでPush、2のクエリでPop。
注意すべきは、)が(の数を超えると、それより末尾にどのような文字を追加されたり削除されても必ず「良い括弧列」にはなり得ない。なぜならStack方式で追加と削除が行われるから。
(の数をpx、)の数をsxとする。
1のクエリでpx < sxになる直前のpx,sxを保持し、2のクエリでそのpx,sxと同値にならない限りそれ以降を無視する仕組みを考えればよい。
(が前置、)が後置なのだから、prefixとsuffixでいいか、などと思っていたけどそんなに合致してないかも。
所感
良い括弧列ではない)(が登場する時の扱いとstack方式のデータ型を知っていれば、判定処理の場合分けをきっちりすることと実装がそこそこ面倒なだけでちゃんと解けそうな気がします。この問題の場合は探索の必要はないですし。
コメント