問題:AtCoder Beginner Contest 131: D - Megalomania
公式解説PDF:https://img.atcoder.jp/abc131/editorial.pdf
公式解説動画:https://youtu.be/XI8exXVxZ-Q?t=4046
解説
締切が早い仕事から順に終わらせていく貪欲法です。割と直感で思いつく解法ですが、なぜそれでよいのかの証明は解説PDFが詳しいです。
あんまり書くことないのですが、入力例1を考えてみます。
仕事i | 仕事を終わらせるのに必要な時間 | 締切時刻 |
---|---|---|
0 | 2 | 4 |
1 | 1 | 9 |
2 | 1 | 8 |
3 | 4 | 9 |
4 | 3 | 12 |
これを、締切が早い順に仕事を終わらせた場合、以下のようになります。
時刻 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
終わった仕事i | 0 | 2 | 1 | 3 | 4 |
すべて締切に間に合います。
たとえば別の方法として、「仕事を終わらせるのに必要な時間が短いやつから終わらせていく」というのを思いつきますが、これだとたとえば、
i | 仕事を終わらせるのに必要な時間 | 締切時刻 |
---|---|---|
0 | 2 | 3 |
1 | 1 | 3 |
2 | 1 | 4 |
といった場合に、
時刻 | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
終わった仕事i | 1 | 2 | 0 |
となりますが、これは仕事0は締切時刻3に間に合っていません。
上の例を、締切が早いやつ順に仕事を終わらせてみると、
時刻 | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
終わった仕事i | 0 | 1 | 2 |
となり、これはすべて締切に間に合っています。
コーナーケース
- 特になし
実装
# -*- coding:utf-8 -*- class Work(): """ 仕事クラス """ def __init__(self, a, b): self.need_time = a # 仕事を終わらせるのに必要な時間 self.deadline = b # 締切時刻 def solve(): N = int(input()) works = [] # 仕事をリストにぶちこむ for _ in range(N): a, b = list(map(int, input().split())) works.append(Work(a, b)) works.sort(key=lambda x: x.deadline) # 締切が早い順にソート # 締切が早いやつから先に仕事を終らせる貪欲法 now_time = 0 # 現在時刻 for i in range(N): now_time += works[i].need_time if now_time > works[i].deadline: print("No") return print("Yes") if __name__ == "__main__": solve()
計算量は です。
ちなみにですが、問題の制約は となっていますので、まあ大体N=105くらいならPythonはで2秒の制約で解けるので、 で解く方法はないかな、とあたりをつけることができます。Pythonで N=106 はギリギリなイメージです。
参考
- リストの要素がクラスオブジェクトの場合のソート(Python) - ベスパリブ
- 過去の自分が役に立ったっていう