在庫の入庫と出庫と取り消しを処理する

配列の処理
問題 20
ふつう
目安 31 分

入庫、出庫、取り消しの命令を順に処理して、最後の在庫を品名の順に出す。取り消しのたびにやり直さず、成功した命令の履歴を積んでおいて戻す練習です。

本番の試験は PC で受けることが多いので、PC での練習をすすめます。スマホでも、読んで、書いて、採点するところまで動きます。

入力は標準入力から読み、答えは標準出力に書きます。1 テストあたり 3 秒までです。

問題

倉庫の在庫を、N 個の命令を上から順に処理して管理します。はじめは、どの品の在庫も 0 個です。命令は次の 3 種類です。

IN s x 品 s を x 個入庫します。品 s の在庫が x 個増えます
OUT s x 品 s を x 個出庫します。品 s の在庫が x 個以上あれば、在庫が x 個減ります。在庫が x 個より少なければ、何も起きません (この出庫は失敗です)
UNDO 取り消しです。成功した入庫と出庫のうち、まだ取り消していないもので最も新しい 1 つを取り消します。入庫を取り消すと、その品の在庫が x 個減り、出庫を取り消すと、その品の在庫が x 個増えます。取り消せる命令が 1 つも無ければ、何も起きません

失敗した出庫と、取り消し (UNDO) そのものは、取り消しの対象になりません。一度取り消した命令を、もう一度取り消すこともありません。

全部の命令を処理したあとの在庫を出力してください。

入力の形式

N
命令 1
命令 2
...
命令 N

1 行目に命令の数 N、続く N 行に、1 行に 1 つの命令が並びます。命令の中の語は半角の空白 1 つで区切られています。

出力の形式

在庫が 1 個以上ある品を、品名の辞書順 (英小文字の a から z の順に 1 文字目から比べ、短いほうが先に終わるならそちらが先) に、1 行に 1 品ずつ、品名と在庫の数を半角の空白 1 つで区切って書きます。在庫が 1 個以上ある品が 1 つも無ければ、EMPTY と 1 行だけ書きます。

制約

N は 1 以上 200000 以下の整数です
品名 s は英小文字だけからなる、1 文字以上 10 文字以下の文字列です
個数 x は 1 以上 1000000 以下の整数です

入力と出力の例

例 1

apple を 5 個、pen を 3 個入れたあと、apple を 2 個出して 3 個になります。pen を 10 個出そうとしますが、3 個しか無いので失敗します。次の取り消しは、失敗した出庫ではなく、その前の apple の出庫を取り消すので、apple は 5 個に戻ります。pen を 1 個出して 2 個になり、最後の取り消しでその出庫が戻って 3 個になります。

入力

7
IN apple 5
IN pen 3
OUT apple 2
OUT pen 10
UNDO
OUT pen 1
UNDO

出力

apple 5
pen 3

例 2

最初の取り消しは、取り消せる命令が無いので何も起きません。cup を 2 個入れて 2 個出すと在庫は 0 個になり、出力する品がありません。

入力

3
UNDO
IN cup 2
OUT cup 2

出力

EMPTY

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

全部のテストに通ると、解答と考え方が開きます。

先にヒントを試すと、自分で解けた手応えが残ります。どうしても詰まったときは、ここから開けます。

解答

在庫を辞書で持ち、成功した入庫と出庫を (品名, 増え方) の組で履歴のスタックに積みます。失敗した出庫は積みません。取り消しでは、スタックが空でなければ末尾を取り出して、在庫からその増え方を引きます。最後に、在庫が 1 個以上の品名を並べ替えて出力します。1 つの命令は O(1) で処理でき、並べ替えを合わせて全体で O(N log N) です。

Python

import sys

lines = sys.stdin.read().split("\n")
n = int(lines[0])
stock = {}
history = []
for i in range(n):
    parts = lines[1 + i].split()
    if parts[0] == "UNDO":
        if history:
            name, change = history.pop()
            stock[name] -= change
        continue
    name, count = parts[1], int(parts[2])
    if parts[0] == "IN":
        stock[name] = stock.get(name, 0) + count
        history.append((name, count))
    elif stock.get(name, 0) >= count:
        stock[name] -= count
        history.append((name, -count))

names = sorted(name for name, count in stock.items() if count > 0)
if names:
    print("\n".join(f"{name} {stock[name]}" for name in names))
else:
    print("EMPTY")

JavaScript

const lines = require("fs").readFileSync(0, "utf8").split("\n");
const n = Number(lines[0]);
const stock = new Map();
const history = [];
for (let i = 0; i < n; i++) {
  const parts = lines[1 + i].trim().split(" ");
  if (parts[0] === "UNDO") {
    if (history.length > 0) {
      const [name, change] = history.pop();
      stock.set(name, stock.get(name) - change);
    }
    continue;
  }
  const name = parts[1];
  const count = Number(parts[2]);
  const have = stock.get(name) ?? 0;
  if (parts[0] === "IN") {
    stock.set(name, have + count);
    history.push([name, count]);
  } else if (have >= count) {
    stock.set(name, have - count);
    history.push([name, -count]);
  }
}

const names = [...stock.keys()].filter((name) => stock.get(name) > 0).sort();
console.log(names.length > 0 ? names.map((name) => `${name} ${stock.get(name)}`).join("\n") : "EMPTY");

計算量

時間は O(N log N) です。命令ごとの処理は辞書の読み書きとスタックの出し入れだけで O(1) です。最後の並べ替えに O(N log N) かかります。遅くなるのは、取り消しのたびに、取り消していない成功した命令を最初から全部当て直して在庫を作り直す書き方です。1 回の取り消しに O(N) かかり、取り消しが多い入力では O(N^2) になります。たとえば入庫を 10 万回したあとに入庫と取り消しを 5 万回ずつ繰り返すと、50 億回ほどの当て直しになって時間切れになります。

よくある間違い

失敗した出庫も履歴に積んでしまい、次の取り消しが何も戻さなくなる。失敗した出庫は積みません
履歴が空のときに取り消しで末尾を取り出そうとして、エラーで止まる
在庫が 0 個になった品まで name 0 と出力してしまう。出すのは 1 個以上の品だけです
出力する品が無いときに何も書かない。EMPTY と書く決まりです
品名を、出てきた順のまま出力してしまう。辞書順に並べ替えます

解答を動かした版 Python 3.12.14Node.js 22.23.4確認日 2026/10/31

main.py

import sys

lines = sys.stdin.read().split("\n")
n = int(lines[0])
commands = [lines[1 + i].split() for i in range(n)]

# ここから書く

入力

7
IN apple 5
IN pen 3
OUT apple 2
OUT pen 10
UNDO
OUT pen 1
UNDO

出力

「実行する」を押すと、ここに出力が出ます

できているか「提出して採点」を押すと、隠れたテストを全部走らせて、通ったかをここに出します