AtCoder が提供しているABC（AtCoder Beginner Contest）320 のE問題をC++とPythonで解いてみました。ABC320は、2023年9月16日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Somen Nagashi（Difficulty : 1096）
問題はリンク先をご覧ください。
set コンテナや優先度付きキューを使って状況をシミュレートします。AtCoder Problems による Difficulty は 1096 でした。
解答案
基本的な処理は以下となります。row と wait の二つのコンテナを用意します。
- コンテナ row には、列で待っている人を格納します。そうめんを流すタイミングで、一番小さい数字（人）を取り出します。初期値として、1 から N までを格納します。
- コンテナ wait には、そうめんを得て列から外れて待つ人を格納します。具体的には、(列に戻る時間, 戻る人) を組で格納します。初期値は、空です。
- 次にコンテナ wait の要素から、列に戻る時間が早い順番に要素を取り出し、次にそうめんを流すタイミングより前に列に戻る時間の人を row に格納していきます。
コンテナ row と wait では、以下の操作が必要となります。
- 一番小さい要素を取り出す。
- コンテナには要素が追加される。
C++ では set または priority_queue を、Python では、heapq を選択すると、この操作を速く行うことができます。
C++ プログラム例（ABC320E）
set コンテナを使います。上で整理した手順を繰り返します。
- wait に格納されている要素を（戻る時間が早い順に）取り出して、次にそうめんを流すタイミングより前であれば、row に人を格納して、wait から要素を削除します（24ー27行目）。
- そうめんが流すタイミングで、row に人がいれば、一番数字が小さい人を取り出して、そうめんの量 wi を加えます。そうめんを得たひとは、戻る時間と合わせて wait に格納して、row から削除します（28ー32行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n, m;
cin >> n >> m;
vector<int> t(m), s(m);
vector<ll> w(m);
for (int i = 0; i < m; ++i) {
cin >> t[i] >> w[i] >> s[i];
}
set<int> row;
for (int i = 1; i <= n; ++i) {
row.insert(i);
}
set<pair<int, int>> wait;
vector<ll> result(n + 1, 0);
for (int i = 0; i < m; ++i) {
while ((!wait.empty())&&((*(wait.begin())).first <= t[i])) {
row.insert((*(wait.begin())).second);
wait.erase(*(wait.begin()));
}
if (!row.empty()) {
result[*(row.begin())] += w[i];
wait.insert(make_pair(t[i] + s[i], *(row.begin())));
row.erase(*(row.begin()));
}
}
for (int i = 1; i <= n; ++i) {
cout << result[i] << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC320E）
Python には、C++ の set に該当する順序付き集合がありません。ただし、この問題は、優先度付きキュー heapq を使っても解くことができます。
優先度付きキューを使いますが、基本的な考え方は、C++ 版と同じです。列に並んでいる人の番号を格納するキュー row と、待ち行列を管理するキュー wait を用意して、C++ と同じ処理を行います。ただし、heapq は、heappop でキューから値を削除するため、取り出すべきでない場合には、同じ値を heappush で書き戻します（23行目）。
"""AtCoder Beginner Contest 320 E"""
import heapq
n, m = map(int, input().split())
t = [0] * m
w = [0] * m
s = [0] * m
for i in range(m):
t[i], w[i], s[i] = map(int, input().split())
row = list(range(1, n + 1))
heapq.heapify(row)
wait = []
heapq.heapify(wait)
result = [0] * (n + 1)
for i in range(m):
while len(wait) > 0:
wt = heapq.heappop(wait)
if wt[0] <= t[i]:
heapq.heappush(row, wt[1])
else:
heapq.heappush(wait, wt)
break
if len(row) > 0:
rt = heapq.heappop(row)
result[rt] += w[i]
heapq.heappush(wait, (t[i] + s[i], rt))
for i in range(1, n + 1):
print(result[i])こちらも「AC」と判定されました。
最後に
E問題は、適切なコンテナを選択して状況をシミュレートすることができました。
ABC320は、ABCDEの5問を解くことができて、パフォーマンス 1200 と評価されました。レートも 938 と最高を更新することができました。このような進歩を時々感じることができるため、のんびり ABC 参加を続けようと思います。
引き続き ABC の問題を紹介していきます。
