ベスパリブ

プログラミングを主とした日記・備忘録です。ベスパ持ってないです。

ABC 131: D問題の解説 (Python3)

問題: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()

計算量は O(N) です。

ちなみにですが、問題の制約は  1 ≤ N ≤ 2×10^5 となっていますので、まあ大体N=105くらいならPython O(N)で2秒の制約で解けるので、 O(N) で解く方法はないかな、とあたりをつけることができます。Pythonで N=106 はギリギリなイメージです。

参考