Google Code Jam Japan 2011 B: 最高のコーヒー

GCJ

問題概要

N(<100)種類あるコーヒーがあり、残量、消費期限、満足度が設定されている。1日1杯だけどれかのコーヒーを飲める。K(<10^12)日間で得られる満足度の最大値を求める問題。

考えたこと

  • これはgreedyっぽい。
  • どれをどれだけ飲むか決めれば、後は消費期限の短いやつから飲んでいけばいいので消費期限でソート？
  • いやいやそれは動的計画法の考え方だ。もちろん満足度の大きい順にソートすべきだ。
  • ちょっと落ち着くためにsmall書こう。N=K=8なのでO(N^K * N)の全探索を書く。
  • よし落ち着いた。満足度の高い順に使えるだけ使う。ただし使える日が複数あるなら可能な限り飲むタイミングを遅らせる。
  • 計算量は大雑把に見積もってO(N^3)くらい？でも区間を持って色々するので面倒そうだしバグ死する自信がありすぎる…
  • しかしほかに方法も思いつかないので書く。その後small解との食い違いが判明してバグを訂正するのに30分くらいかかった。

通ったコード

small

import std.stdio;
import std.algorithm;

int nextInt(){
	int x;
	scanf("%d",&x);
	return x;
}

long nextLong(){
	long x;
	scanf("%lld",&x);
	return x;
}

int[] cs, ts, ss;
int N, K;

int solve(){
	N = nextInt;
	K = nextInt;

	cs = new int[N];
	ts = new int[N];
	ss = new int[N];

	for(int i=0; i<N; i++){
		cs[i] = nextInt;
		ts[i] = nextInt;
		ss[i] = nextInt;
	}

	return dfs(1);
}

int dfs(int day){
	if(day == K + 1){
		return 0;
	}

	int ret = 0;

	for(int i=0; i<N; i++)if(cs[i] > 0 && day <= ts[i]){
		cs[i]--;
		ret = max(ret, ss[i] + dfs(day + 1));
		cs[i]++;
	}

	return ret;
}

void main(){
	for(int c=1, T=nextInt; c<=T; c++){
		writef("Case #%d: %d\n", c, solve());
	}
}

large

import std.stdio;
import std.algorithm;

int nextInt(){
	int x;
	scanf("%d",&x);
	return x;
}

long nextLong(){
	long x;
	scanf("%lld",&x);
	return x;
}

long solve(){
	int N = nextInt;
	long K = nextLong, ans = 0;

	struct Coffee {
		long c, t, s;
	}

	Coffee[] cofs;
	for(int i=0; i<N; i++){
		cofs ~= Coffee(nextLong, nextLong, nextLong);
	}

	sort!("a.s > b.s")(cofs);

	struct Range { //[from, to] (閉区間!)
		long from, to;
	}

	Range[] cur;
	cur ~= Range(1, K);

	foreach(Coffee cof; cofs){
		Range[] next;
		long res = cof.c;

		foreach(Range r; cur){
			long len = r.to - r.from + 1;
			if(len <= 0) continue;
			if(res > 0){
				if(r.from <= cof.t && cof.t < r.to){ //消費期限が途中できれる
					next ~= Range(cof.t + 1, r.to);
					r = Range(r.from, cof.t);
					len = r.to - r.from + 1;
				}

				if(r.to <= cof.t){ //消費期限は大丈夫
					if( res < len ){ //全部飲む
						ans += res * cof.s;
						next ~= Range(r.from, r.to - res);
						res = 0;
					}
					else{
						ans += len * cof.s;
						res -= len;
					}
				}
				else{ //消費期限が切れている
					next ~= r;
				}
			}
			else{
				next ~= r;
			}
		}

		cur = next;
		sort!("a.from > b.from")(cur);
	}

	return ans;
}

void main(){
	for(int c=1, T=nextInt; c<=T; c++){
		writef("Case #%s: %s\n", c, solve());
	}
}