AIで解説 AtCoder攻略　スタック・キュー

スタック・キューページの位置づけ

項目	内容
必修度	重要
学習目安	標準
前提	list・deque
対象問題	30問（推定値あり30問、未算出0問）

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

学習目安	difficulty推定値	問題数
入門	difficulty < 0	4
標準	0〜799	15
標準〜発展	800〜1199	6
発展	1200以上	5
未算出	—	0

直前に追加した要素や、先に入った要素を順番どおり処理します。隣接する同種要素をまとめると、長い列も一度の走査で扱えます。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

スタック・キューの見分け方

最後に入れたものから取り出す
先に入れたものから取り出す
隣接要素の削除・結合を繰り返す

スタック・キューの実装前チェック

追加と取り出しの順番を図にする
空のスタック・キューを確認する
同じ値をまとめる単位を決める

先に確認する文法・ライブラリ

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

代表問題で実装を確認する

最初の一問として、ABC247 D G. Cylinder（公式解説）を解きます。同じ値が連続して並ぶ部分を(値,個数)としてdequeに保存します。先頭から必要な個数だけ取り出すので、1個ずつ展開しません。

from collections import deque

Q = int(input())
queue = deque()
for _ in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        _, x, c = query
        queue.append([x, c])
    else:
        _, c = query
        answer = 0
        while c:
            x, count = queue[0]
            take = min(c, count)
            answer += x * take
            c -= take
            if take == count:
                queue.popleft()
            else:
                queue[0][1] -= take
        print(answer)

各グループを追加・削除する回数が高々Qなので、全体O(Q)時間・O(Q)メモリです。

スタック・キューの学ぶ順番

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

まず解く

問題	公式解説	出題意図	difficulty
ABC419 B Get Min	公式解説	公式Editorialの方針を get min deque として整理する。	-624
ABC396 B Card Pile	公式解説	Simulate card insertion and removal from piles using stack-like containers.	-556
ABC358 B Ticket Counter	公式解説	Official editorial intent is classified as queue service simulation.	-490
ABC433 B Nearest Taller	公式解説	公式Editorialの方針を nearest taller stack として整理する。	-454
ABC351 C Merge the balls	公式解説	Official editorial intent is classified as equal stack merge.	175

次に解く

問題	公式解説	出題意図	difficulty
ABC413 C Large Queue	公式解説	公式Editorialの方針を run-length queue として整理する。	177
ABC394 D G. Colorful Bracket Sequence	公式解説	Use a stack to match colored opening and closing brackets and validate the sequence.	216
ABC389 C Snake Queue	公式解説	蛇の各要素をキューへ追加し、先頭からの累積オフセットで位置クエリに答える。	220
ABC447 D Take ABC 2	公式解説	Use a stack to erase every newly formed ABC pattern.	430
ABC283 D G. Scope	公式解説	Push a new scope on ‘(‘ and remove its variables on ‘)’; reject a variable reused in any active scope.	453

挑戦問題

問題	公式解説	出題意図	difficulty
ABC247 D G. Cylinder	公式解説	同じ値の個数をまとめたキューから指定個数だけ取り出し、値の総和を計算する。	468
ABC428 C Brackets Stack Query	公式解説	公式Editorialの方針を bracket stack query として整理する。	483
ABC237 D G. LR insertion	公式解説	Lなら左、Rなら右へiを追加する操作をdequeで行い、最終列を出力する。	544
ABC328 D G. Take ABC	公式解説	Use a stack to remove every newly formed ABC substring.	555
ABC240 D G. Strange Balls	公式解説	同じ数字の連続個数をスタックで持ち、個数が数字に達した塊を消して残数を出力する。	570