D - アルバイトのシフト割り当て / Assignment of Cooking Tasks Editorial
by 
MMNMM
（必要）スキルレベルの昇順に、タスクとスタッフを並べることを考えます。 タスクの必要スキルレベルとスタッフのスキルレベルが等しいとき、タスクのほうを先に並べます。 すると、それぞれのスタッフは自分より先に並んでいるタスクをすべて担当することができ、後ろに並んでいるタスクは担当できません。
この列を先頭から見てゆき、次のような処理を行います。
- いま見ているものがタスクなら、机の上にそのタスクを置く。
- いま見ているものがスタッフなら、机の上にタスクが \(1\) つ以上あればそのスタッフが机の上のタスクをどれか 1 つ担当し、机の上から担当したタスクを持っていく。机の上にタスクがなければそのスタッフにタスクは割り当てられない。
この割り当てが最適になることを示します。
証明
全スタッフがタスクを担当できた場合、これは明らかに最適です。
そうでない場合、タスクを担当できなかった最後のスタッフ \(S\) について考えます。 スタッフ \(S\) より先に並んでいるタスクの個数を \(n\) 個とし、スタッフ \(S\) より後に並んでいるスタッフの人数を \(m\) 人とします。
スタッフ \(S\) 自身およびスタッフ \(S\) より先に並んでいるスタッフは、スタッフ \(S\) より先に並んでいるタスクしか担当できません。 よって、スタッフ \(S\) 自身およびスタッフ \(S\) より先に並んでいるスタッフのうち、\(n\) 人までしかタスクを担当できません。 それ以外のスタッフ \(m\) 人は全員タスクを担当しているので、スタッフのうち \(n+m\) 人までしかタスクを担当できないことがわかります。 スタッフ \(S\) はタスクを担当できていないので、スタッフ \(S\) までに \(n\) 個のタスクがすべて割り当てられていることから、\(n+m\) 人がタスクを担当できていることがわかり、この割り当て方が最適であることが示されました。
残っているタスクがどれであるかや、スタッフが机の上のタスクのどれを持って行ったかは答えに影響しないことに注意してください。 つまり、机の上に現在いくつタスクがあるかだけを管理すればよいです。
ソートがボトルネックとなり、時間計算量は \(O((N+M)\log(N+M))\) となります。
あとは、この処理をプログラムに直すことでこの問題を解くことができます。
実装例は以下のようになります。
#include <iostream>
#include <vector>
#include <algorithm>
#include <ranges>
using namespace std;
int main(){
int N, M, C;
cin >> N >> M >> C;
vector<int> staff(N), task(M);
for (auto&& A : staff) {
cin >> A;
}
for (auto&& B : task) {
cin >> B;
}
// 同じスキルレベルならタスクのほうが前になるように、(スキルレベル, タスクなら 0 スタッフなら 1) を並べる
vector<pair<int, int>> staff_and_task;
for (const auto A : staff) {
staff_and_task.emplace_back(A, 1);
}
for (const auto B : task) {
staff_and_task.emplace_back(B, 0);
}
// スキルレベルが低いものから並べる
ranges::sort(staff_and_task);
int ans = 0, remaining_tasks = 0;
for (const auto type : staff_and_task | views::elements<1>) { // 前から順に見ていって
if (type == 0) { // タスクなら
++remaining_tasks; // 残りタスク数を増やす
} else if (remaining_tasks > 0) { // スタッフで、タスクが残っていたら
--remaining_tasks; // タスクを取って、
++ans; // 割り当てた個数を増やす
}
}
cout << static_cast<long>(ans) * C << endl; // C 倍して出力（オーバーフローに注意）
return 0;
}
N, M, C = map(int, input().split())
staff = list(map(int, input().split()))
task = list(map(int, input().split()))
# 同じスキルレベルならタスクのほうが前になるように、(スキルレベル, タスクなら 0 スタッフなら 1) を並べたリストを作る
staff_and_task = [(A, 1) for A in staff] + [(B, 0) for B in task]
# スキルレベルが低いものから並べる
staff_and_task.sort()
ans = 0
remaining_tasks = 0
for _, type in staff_and_task: # 前から順に見ていって
if type == 0: # タスクなら
remaining_tasks += 1 # 残りタスク数を増やす
elif remaining_tasks > 0: # スタッフで、タスクが残っていたら
remaining_tasks -= 1 # タスクを取って、
ans += 1 # 割り当てた個数を増やす
print(ans * C) # C 倍して出力
posted:
last update: