スタックとキューは、値を入れたあと「どれが先に取り出されるか」で見分けます。たとえば 2、3の順に入れ、最初に3が出るなら後入れ先出し（LIFO）のスタック、最初に2が出るなら先入れ先出し（FIFO）のキューです。ABC247 D – Cylinderは右から追加して左から取り出すFIFOの問題です。値を1個ずつ並べず、値と個数の組をdequeに置くと、部分的な取り出しも扱えます。
| 構造 | 2、3の順に入れたとき、先に出る値 |
取り出し順 |
|---|---|---|
| スタック | 3 |
後入れ先出し（LIFO） |
| キュー | 2 |
先入れ先出し（FIFO） |
ABC247 Dは右から入れて左から取り出す
正式な問題名はABC247 D – Cylinderの公式問題です。空の筒にクエリを順に適用します。1 x cは値xのボールを右端からc個入れる操作、2 cは左端からc個取り出し、その値の合計を出力する操作です。キューと同じく、先に入れたボールほど先に取り出します。
- クエリ数は
1 <= Q <= 2*10^5です。 - 値は
0 <= x <= 10^9、個数は1 <= c <= 10^9です。入力は整数です。 2 cを行う時点で、筒には少なくともc個のボールがあります。
1回の追加で最大10^9個を入れられるため、ボールごとに要素を作ると個数に比例した処理になります。代わりに、追加クエリ1 x cを(x, c)という1つのgroup（同じ値のまとまり）として保存します。collections.dequeの右端へappendし、左端のgroupから取り出せば、筒内の順序もそのまま保てます。
公式サンプル1で部分消費とgroup跨ぎを見る
以下のdequeは左端が先頭、右端が末尾です。各組は(値, 残り個数)を表します。type 2では、先頭groupから必要な個数だけ消費します。
| クエリ | 処理 | 処理後のdeque | 出力 |
|---|---|---|---|
1 2 3 |
値2を3個追加します。 |
[(2, 3)] |
— |
2 2 |
(2, 3)から2個消費するので、合計は2 * 2 = 4。1個残ります。 |
[(2, 1)] |
4 |
1 3 4 |
値3を4個、右端に追加します。 |
[(2, 1), (3, 4)] |
— |
2 3 |
まず(2, 1)を全消費して2を加え、次に(3, 4)から2個を部分消費して3 * 2 = 6を加えます。合計は2 + 6 = 8です。 |
[(3, 2)] |
8 |
最初の取り出しではgroupの一部だけを残し、次の取り出しでは先頭groupを使い切ってから次のgroupへ進みます。groupの順番と残数を更新すれば、個々のボールを展開しなくても筒の状態を再現できます。
Pythonの完全な参考コード
import sys
from collections import deque
def solve():
data = list(map(int, sys.stdin.buffer.read().split()))
if not data:
return
q = data[0]
pos = 1
groups = deque()
answers = []
for _ in range(q):
query_type = data[pos]
pos += 1
if query_type == 1:
x = data[pos]
count = data[pos + 1]
pos += 2
groups.append((x, count))
else:
remaining = data[pos]
pos += 1
total = 0
while remaining:
x, count = groups[0]
take = min(remaining, count)
total += x * take
remaining -= take
if take == count:
groups.popleft()
else:
groups[0] = (x, count - take)
answers.append(str(total))
if answers:
sys.stdout.write("\n".join(answers) + "\n")
if __name__ == "__main__":
solve()
コードが保つ状態と正しさ
groupsの各タプルは、筒に残る同じ値のボールをまとめています。dequeの並びは筒の左から右への順序、タプルの個数はその値の残数です。クエリを処理する間も、この対応が崩れないことが不変条件です。
| コードの箇所 | 役割 |
|---|---|
sys、deque、solve() |
sysで標準入力・標準出力を扱い、両端操作のできるdequeを使います。solve()は1回分のquery処理をまとめます。 |
if not data |
入力が空なら処理を終え、data[0]を読む前に戻ります。 |
data、q、pos |
標準入力を整数列として読み、query数と次に読む位置を管理します。 |
groups、answers |
groupsは残っている筒、answersはtype 2の合計をquery順に保存します。 |
for _ in range(q)とquery_type |
queryを1つずつ読み、type 1とtype 2の処理へ分けます。 |
| type 1の分岐 | xとcountを読み、(x, count)をgroups.appendで末尾へ加えます。 |
| type 2の分岐 | remainingを必要数c、totalを今回の合計として初期化します。 |
while remaining |
先頭の(x, count)からtake = min(remaining, count)個を取り、x * takeを足して残り必要数を減らします。 |
take == countの分岐 |
groupを使い切ったときはpopleftで先頭を削除し、一部だけなら先頭の個数をcount - takeに更新します。 |
answersへの追加と標準出力 |
答えをquery順に改行出力し、answersが空なら何も出しません。 |
if __name__ == "__main__" |
ファイルをプログラムとして実行したときにsolve()を呼びます。 |
type 1は筒の右端へgroupを追加します。type 2の各反復では、先頭からmin(残り必要数, groupの残り個数)個を取り出して合計し、使い切ったgroupを削除するか残数を減らします。公式条件では取り出す個数を満たすだけのボールが必ずあるため、groups[0]が空のdequeを指すことはありません。したがって、処理後のdequeは未処理の筒と一致し、type 2の答えも取り出した個数分の値の合計になります。
連続する追加の値が同じでも、コードはgroupを結合せず別々に置きます。たとえば(7, 2)と(7, 3)は、同じ値が合計5個続く状態を2つに分けて表したものです。左から順に消費すれば、合計も残りの順序も1groupにまとめた場合と同じです。各追加queryが最大1groupを作るので、結合しなくてもgroup数はQ以下です。ABC247 Dの公式個別解説もRun Length encodingで管理する方法を示し、同じ値の連続groupを結合しなくても全体の計算量は変わらないと説明しています。
計算量
各追加queryはappendを1回行います。取り出しのループは、使い切ったgroupを1つpopleftするか、最後のgroupを一部だけ消費してremainingが0になるかで終わります。各groupは一度だけ追加され、完全消費で削除されるのも高々一度です。一方、部分消費は1回のtype 2につき高々1groupなので、その更新も全queryを通じて高々Q回です。よって全体の時間はO(Q)です。公式個別解説も、追加をO(1)、取り出しをO(1 + 取り出したgroup数)、全体をO(Q)として整理しています。
groupsの要素数は追加query数以下、answersの要素数は取り出しquery数以下です。入力配列も整数を高々定数個ずつ持つため、追加メモリ全体はO(Q)、dequeが保持するgroupのメモリもO(Q)です。公式サンプル2のように10^9個をまとめて扱えるため、実際のボール数に比例した展開は不要です。
掲載コードの標準入力での出力
公式サンプル3件と独自に作った境界例2件を、上のコードへ標準入力として与えた結果です。公式サンプルと独自例を分けています。
| 入力の区分 | ケース | 標準出力 |
|---|---|---|
| 公式 | サンプル1 | 48 |
| 公式 | サンプル2 | 1000000000000000000 |
| 公式 | サンプル3 | queryは追加のみのため出力行なし |
| 独自境界例 | 部分消費、全消費、group跨ぎ、同値連続追加 | 5155247 |
| 独自境界例 | x = 0、c = 10^9 |
0 |
スタックかキューかは、最初に入れた値と後から入れた値のどちらを先に取り出すかで判定できます。ABC247 Dでは先入れのgroupから消費するので、FIFOの順序を守りながら先頭の残数を更新することが実装の中心です。
