DDPC B - DDPC特別ビュッフェⅡ

内容

• DDPC B問題 "DDPC 特別ビュッフェII"を、pythonで解いた。
• にぶたんのメモ。

問題

atcoder.jp

考えたこと

• 条件を満たす最小時間を求めろ。
• 美味しさが高いものから食べていけばよさそう。
• 二分探索でいけるのでは ?と思い、二分探索

ポイント

• 制限時間があるのがややこしくなる。
  • 時刻を逆から考えることにする
    • hoge分に食べれなくなる-> huga分に食べれるようになる。　 に言い換えることで、heapqを使って実装できる。
    • e.g x分以内に食べ切るとき、Ti>xのものは、最初から食べれる。 Ti<=xのものは、x分間のシミュレーションの中で、x-Ti分以降に食べれるようになる。

      実装

from collections import defaultdict
import heapq

N, X = map(int, input().split())
T = list(map(int, input().split()))
A = list(map(int, input().split()))

foods = [(t, a) for t, a in zip(T, A)]

# D[t]:時刻tに締め切りが来る食べ物の、美味しさのlist
D = defaultdict(list)
for t, a in zip(T, A):
    D[t].append(a)


def check(x):
    """
    return True if x秒で　美味しさX食べれる
    """

    # 食べれる候補
    Q = []
    tmp = 0

    #　最初から食べれるもの
    for t, a in foods:
        if t > x:
            heapq.heappush(Q, -a)

    # 0~x 秒まで、何を食べるかシミュレート
    for i in range(x):
        # add
        for v in D[x-i]:
            heapq.heappush(Q, -v)

        if len(Q) == 0:
            continue
        #　現時点でもっとも美味しい物を食べる
        cur = -heapq.heappop(Q)
        tmp += cur

    # 美味しさの和が　X以上ならTrue
    return tmp >= X


low = 0
high = 10**5+1

while low <= high:
    mid = (low+high)//2
    if check(mid):
        high = mid-1
    else:
        low = mid+1

if check(low):
    print(low)
else:
    print(-1)

終わりに