Google Code Jam Japan 2011 予選 B

python program

問題

https://code.google.com/codejam/contest/dashboard?c=889487#s=p1

方針

  • 一番満足度の高いコーヒー(say, ベストコーヒー)は、(出来る限り)全部飲む。
  • この時、ベストコーヒーは、出来る限り後に飲む。
  • 何故なら、先に飲んじゃうと、二番目に満足度の高いコーヒー(say, セカンドコーヒー)を飲む機会を逸するかもしれないから
    • 例えば、残り2日間で、ベストコーヒー=(残り一杯, 賞味期限2日), セカンドコーヒー=(残り一杯, 賞味期限1日)の場合。

上の方針に従って、最も満足度の高いコーヒーから順番にスケジュールを組んで行くと、最適解になる、と直感的に思って実装して提出したら合ってたんで、多分、合ってるんではないか。

実装

#!/usr/bin/env python

import sys

ifs = open(sys.argv[1])
num = int(ifs.readline().strip())



class Solve:
    def __init__(self, ifs):
        self.N, self.K = map(int, ifs.readline().split())
        self.info      = range(self.N) # cups, days, satisfaction
        for i in range(self.N):
            self.info[i] = map(int, ifs.readline().split())
        self.info.sort(key=lambda a:a[2])
        ## print self.N, self.K
        ## print self.info

    def solve(self):
        self.ans = 0
        while self.N > 0 and self.K > 0:
            self.process_one()
        return self.ans

    def process_one(self):
        self.N -= 1
        best      = self.info[self.N]
        self.info = self.info[:self.N]
        if best[1] <= 0: return
        best_end = min(best[1], self.K)
        best_start = max(best_end - best[0] + 1, 1)
        self.K -= best_end - best_start + 1
        for i in range(self.N):
            if self.info[i][1] < best_start:
                None
            elif self.info[i][1] < best_end:
                self.info[i][1] = best_start - 1
            else:
                self.info[i][1] = best_start - 1 + self.info[i][1] - best_end
        self.ans += (best_end - best_start + 1) * best[2]






for i in range(num):
    obj = Solve(ifs)
    print 'Case #%(n)d: %(ans)d' % {'n':(i+1), 'ans':obj.solve()}