AtCoder が提供しているABC（AtCoder Beginner Contest）325 のD問題をC++とPythonで解いてみました。ABC325は、2023年10月21日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Printing Machine（Difficulty : 1367）
問題はリンク先をご覧ください。
優先度付きキューを使って貪欲法で解きます。AtCoder Problems による Difficulty は、1367 でした。
解答案
基本的な考え方は、「締め切りが近いアイテムから処理する」ことです。貪欲法と呼ぶこともできます。
以下のコンテナを使います。
- それぞれの商品がベルトコンベアに入る時間と出る時間を配列（Vectorコンテナ）に格納します。これは、入る時間でソートします。
- 印字機の範囲に入った商品の出る時間を優先度付きキューに格納します。このキューを使って「締め切りが近いアイテム」から処理をします。キューに格納しても処理できない商品があることに注意です。
C++ プログラム例（ABC325D）
上記の考えで実装します。
- 商品のベルトコンベアに入る時間と出る時間を配列 item に格納します（11ー16行目）。item は入る時間順に処理するためソートします（17行目）。
- item の入る時間順に処理します。一番入る時間が速い商品の時間を now として格納します。その出る時間をキュー que に格納します（25、26行目）。
- 入る時間が同じ now であるすべての商品の、出る時間をすべて que に格納します（27ー34行目）。
- 次に商品が入る時間を変数 next に格納します。next になるまで、商品を印字します。次の商品がない場合は、無限大（INF）に設定します。
- now < next を満たす限り以下を行います。
- now <= 出る時間である限り、その商品は印字できるため、結果（result）を増やします。時間（now）も進めます。
- now > 出る時間であれば、その商品は印字できないため、キューから取り除くだけです。
最後に result の値を出力します。以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF (1LL << 60)
int main()
{
int n;
cin >> n;
vector<pair<ll, ll>> item(n);
for (int i = 0; i < n; ++i) {
ll t, d;
cin >> t >> d;
item[i] = make_pair(t, t + d);
}
sort(item.begin(), item.end());
priority_queue<ll, vector<ll>, greater<ll>> que;
ll now = 0;
ll next = 0;
int index = 0;
int result = 0;
while (index < n) {
now = item[index].first;
que.push(item[index].second);
while (1) {
++index;
if ((index < n)&&(now == item[index].first)) {
que.push(item[index].second);
} else {
break;
}
}
if (index < n) {
next = item[index].first;
} else {
next = INF;
}
while ((now < next)&&(!que.empty())) {
if (now <= que.top()) {
que.pop();
++result;
++now;
} else {
que.pop();
}
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC325D）
基本的な考え方は、C++ と同じです。Python の優先度付きキューの heappop は、値を返す機能も持っています（32行目）。また next は、組込み関数と同名であるため変数名を next_start に変更しました。
"""AtCoder Beginner Contest 325 D"""
import heapq
INF = 1 << 60
n = int(input())
item = [(0, 0)] * n
for i in range(n):
t, d = map(int, input().split())
item[i] = (t, t + d)
item.sort()
que = []
heapq.heapify(que)
index = 0
result = 0
while index < n:
now = item[index][0]
heapq.heappush(que, item[index][1])
while True:
index += 1
if index < n and now == item[index][0]:
heapq.heappush(que, item[index][1])
else:
break
if index < n:
next_start = item[index][0]
else:
next_start = INF
while now < next_start and que:
if now <= heapq.heappop(que):
result += 1
now += 1
print(result)こちらも「AC」と判定されました。
最後に
コンテストでは、E問題を優先しました。残念ながらE問題はWAが取れず、このD問題は、時間切れでした。D問題の提出時間は、22:40:32（32秒遅れ）で、結果もWAでした。ただし、32ビット整数を使っていたのが、WAの原因でした。64ビット整数に修正したプログラムは、ACでした。惜しかったです。
引き続き ABC の問題を紹介していきます。
