roiti46's blog

主に競プロ問題の解説を載せてます

Google Code Jam 2015 Qualification Round: B. Infinite House of Pancakes

問題読解が一番の山だった

問題はこちら

問題

N枚の皿があり、皿iにはPi個のパンケーキが乗っている。通常、1分ごとに各皿に乗っているパンケーキの数は1つ減る。あなたはスペシャルタイムを宣言すれば、ある皿に乗っているパンケーキを空の皿かパンケーキが乗っている別の皿に任意の個数移すことができる(空の皿は十分な枚数あるとする)。各分ごとにあなたはスペシャルタイムを宣言してパンケーキを移す(ただし各皿に乗っているパンケーキは減らない)か通常通りに各皿に乗っているパンケーキを1つ減らすかを選ぶことができる。この条件のもとで、すべてのパンケーキをなくすのに必要な時間の最小値を答えよ。

解法

ある皿に乗っているパンケーキをn枚の皿に均等に分けることは、その皿が1分間に減らすパンケーキの数をn個にするのと同値である。貪欲的に、パンケーキをなくすのにもっとも時間のかかる皿のパンケーキ減少量を増やしていけばいい。スペシャルタイムの宣言回数ごとに、もっとも時間のかかる皿のパンケーキ減少量を1増やし、パンケーキをなくしきるのにかかる時間を計算して、最小値を取っていけばいい。ちょっと重いが、Largeの場合でも30秒ほどで計算が終わる。

T = int(raw_input())
for loop in xrange(T):
    D = int(raw_input())
    P = map(int, raw_input().split())
    ans = max(P)
    P = [[p,1] for p in sorted(P)]

    for divide in xrange(1,1001):
        P[-1][1] += 1
        P = sorted(P, key = lambda x: x[0]/x[1] + (1 if x[0]%x[1] else 0))
        tmp =  P[-1][0]/P[-1][1]+(1 if P[-1][0]%P[-1][1] else 0) + divide
        ans = min(tmp, ans)

    print "Case #%d: %d"%(loop+1, ans)

まとめ

問題設定がぶっ飛んでいた面白い問題だった