AtCoder が提供しているABC（AtCoder Beginner Contest）379 D問題をC++とPythonで解いてみました。ABC379は、2024年11月9日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Home Garden（Difficulty : 745）
問題の詳細は、リンク先をご覧ください。
増加した植物の高さを別管理します。AtCoder Problems による Difficulty は 745 でした。
解答案
2種類目のクエリで鉢に植えてあるすべての植物が $T$ 高くなります。愚直に植物の高さを更新すると、演算量が $O(Q^2)$ となり間に合いません。
このため、高くなった量を別に管理します。
3種類目のクエリでは、植物を高い方から取り出し、それが $H$ より高ければ、その植物を削除して解答する値をひとつ増やします。
植物の高さを管理するコンテナには、以下の性質が必要となります。
- 効率良く挿入できる。
- 効率良く削除できる。
- 一番大きな値を効率よく取り出せる。
優先度付きキューは、この条件を満たします。
C++ プログラム例（ABC379D）
上記の考察に従い、priority_queue を使います。育った植物の高さは、変数 offset として管理します。クエリの処理は以下となります。
offsetの初期値は0とする。- 1種類目のクエリ：
-offsetの値を高さとして登録します。 - 2種類目のクエリ：
offsetの値をt増やす。 - 3種類目のクエリ：
- 植木を高いほうから取り出し、
offsetを考慮して高さがh以上であれば、キューから削除して、変数resultの値をひとつ増やす。 - キューが空になるか、高さが
h未満になると、resultを出力して、クエリ処理を終了します。
- 植木を高いほうから取り出し、
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int q;
cin >> q;
priority_queue<ll> que;
ll offset = 0;
for (int i = 0; i < q; ++i) {
int type;
cin >> type;
if (type == 1) {
que.push(-offset);
} else if (type == 2) {
ll t;
cin >> t;
offset += t;
} else if (type == 3) {
ll h;
cin >> h;
int result = 0;
while (1) {
if ((que.size() != 0) && (que.top() >= h - offset)) {
++result;
que.pop();
} else {
cout << result << endl;
break;
}
}
}
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC379D）
基本的な考え方は同じです。Python では、優先度付きキュー heapq を使います。以下がプログラムです。
"""AtCoder Beginner Contest 379 D"""
import heapq
q = int(input())
que = []
heapq.heapify(que)
offset = 0
for i in range(q):
command = list(map(int, input().split()))
q_type = command[0]
if q_type == 1:
heapq.heappush(que, offset)
elif q_type == 2:
t = command[1]
offset += t
elif q_type == 3:
h = command[1]
result = 0
while True:
if len(que) == 0:
print(result)
break
t_max = -heapq.heappop(que)
if t_max >= h - offset:
result += 1
else:
heapq.heappush(que, -t_max)
print(result)
breakこちらも「AC」と判定されました。
最後に
A、B問題に続けて解き、25分でACを取得できました。自分にとって、速く解くことができてうれしく感じました。
引き続き ABC の問題を紹介していきます。
