ABC379 D問題の解説（Python）

はじめに

この記事では、ABC379のD問題を解説していきます。

ABC（AtCoder Beginner Contest）とは、AtCoderが開催している、競技プログラミングコンテストです。

ABC379　D – Home Garden

問題

問題

十分な個数の植木鉢があります。最初、植物を 1 個も育てていません。

Q 個のクエリが与えられるので、順に処理してください。

クエリは次の 3 種類です。

1. 植物が植えられていない植木鉢を 1 個用意し、その植木鉢に植物を植える。このとき植物の高さは 0 である。
2. T 日待つ。このとき植えてあるすべての植物の高さが T 増加する。
3. 高さが H 以上の植物をすべて収穫し、収穫した植物の数を出力する。収穫した植物は植木鉢から取り除かれる。

制約

• \(1 \leqq Q \leqq 2×10^5\)
• \(1 \leqq T,H \leqq 10^9\)

思考の筋道

すべての植物の高さを直接管理する方法では、TLE（実行時間超過）となってしまいます。

そこでこの問題では、植物の高さの増加に関する累積和を考えましょう。

k 番目のクエリまでで、植物の高さの増加が合計 height[k] だけあったとします。このとき、i 番目のクエリで植えられた植物の j 番目のクエリ時点での高さは height[j] – height[i] で求めることができます。クエリを前から順番に処理していく中で height を管理しておきましょう。

height 以外にもう一つ管理しておかなければならないものがあります。それは、各植物かいつ植えられたかです。k 番目のクエリで植えられた植物をそのまま数値 k として管理しましょう。早い時刻から植えていた植物の方が背が高く、先に収穫される対象となります。すなわち先入先出方式ですので、キューというデータ構造を使って、上記の数値を管理すればよいですね。

以上のことをまとめると、各種類のクエリで行うことは次のようになります。

1. height は変化なし。キューに今のクエリの番号をそのまま保存する（植える）。
2. height を指定分だけ増やす。
3. height は変化なし。先に植えていた植物から高さをチェックし、指定を超えていた場合はキューから取り出す（収穫する）操作を繰り返す。キューから取り出したデータの個数を出力する。

コード

from collections import deque
Q = int(input())

que = deque()
height = [0] * (Q + 1)

for i in range(Q):
  query = list(map(int,input().split()))

  if query[0] == 1:
    height[i + 1] = height[i]
    que.append(i)

  elif query[0] == 2:
    height[i + 1] = height[i] + query[1]

  elif query[0] == 3:
    height[i + 1] = height[i]
    ans = 0
    while que:
      if height[i + 1] - height[que[0]] >= query[1]:
        ans += 1
        que.popleft()
      else:
        break
    print(ans)

以上、ABC379のD問題の解説でした！

では、またね。

リンク