TopCoder SRM 738 Div1 Hard DriveTheCarHard

適当枝刈りで通してしまった。
http://community.topcoder.com/stat?c=problem_statement&pm=15110

問題

車を時間T以内に距離Dの位置まで動かしたい。
初期状態で車の速度は0である。
整数時間に車を整数単位で加速できる。ただし、x加速するにはコストがx^2かかる。

Dまで動かすコストの最小値を答えよ。

解法

一気に加速するとコストが高いので、1ずつ加速すると効率がいい、というのは推測がつく。
実際、T≧300ぐらいのときはそれで間に合う。

以下そうでない場合を考える。
dp(t,d) := 時刻tの時点で、このままいくと時刻Tになってもゴールまで距離dが残りそうなケースにいたる最小コスト
dp(0,D)=0から初めてdp(T,0)を最小にしたい。

時刻tで1加速すると時刻Tまでにゴールまでの距離が(T-t)縮まる。
よって時刻tにおける加速量をaとすると
dp(t+1,max(0,d-(T-t)a)) = min(dp(t+1,max(0,d-(T-t)a)), dp(t,d) + a^2)
の式が成り立つ。
ただ、上記式をDPで解こうとするとt,d,aをループすることになり間に合わない。
そのため何かしら高速化が必要となる。

ここで、aを増やすとコストが急激に増すので効率が急激に下がることは推測がつく。
よって、t,d,を固定してaを増価させる際、値が更新されなくなるあたりでaの総当たりを打ち切ると間に合うようになる。

int from[30303];
int to[30303];

class DriveTheCarHard {
	public:
	int findMinimumFuel(int total_time, int distance) {
		int i;
		if(total_time>=300) {
			
			for(i=1;;i++) {
				distance -= total_time;
				if(distance<=0) return i;
				total_time--;
			}
		}
		FOR(i,30300) from[i]=1LL<<30;
		from[distance]=0;
		while(total_time>1) {
			for(int d=1;d<=distance;d++) if(from[d]<1LL<<30) {
				for(int ac=1;;ac++) {
					int dd=min(d,ac*total_time);
					if(from[d-dd]<=from[d]+ac*ac-50) break;
					from[d-dd]=min(from[d-dd], from[d]+ac*ac);
					if(dd==d) break;
				}
			}
			
			total_time--;
		}
		int ret=1LL<<30;
		FOR(i,distance+1) ret=min(ret,from[i]+i*i);
		return ret;
	}
}

まとめ

Medium落としたのでこっちは通ってよかった…。