TopCoder SRM 647 Div1 Medium CtuRobots

本番かなり苦戦したが何とか解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=13595

問題

N台のロボットがある。
それぞれの価格はcost[i]で、燃料タンクの容量はcap[i]である。

ここで、お金Bを使って買える範囲で何台かのロボットを買い、以下のようにロボットを動かす。

• 購入したロボを順に番号づける。
• 原点から各ロボは一斉にスタートし、同じ方向に移動する。初期状態で各ロボの燃料タンクの中身は満タンである。
• ロボは移動距離１につき燃料を１消費する。
• 各ロボは途中で引き返すことができる。その際、次の番号のロボに一部燃料を渡すことが出来る。
• 各ロボは原点に戻ってこなくてはならない。

１台で良いので、原点からもっとも遠くの点にロボットを移動させ、原点に戻ってこさせたい。
最適なロボの購入および番号付を行った場合、その最遠点の距離を求めよ。

解法

まず、ロボットの燃料が決まっているときどこまで移動できるか考えてみる。
この時、ロボットの番号付および移動のアプローチは以下のようにすると良い。

• 燃料タンクの容量が小さい順に番号を振る。たとえばi番の容量はC[i]とする。
• 最後以外のi番目のロボは、(i+1)番のロボのタンクを再度満タンに出来、かつ自分が原点に戻れる燃料を残せる位置まで移動して引き返す。

この時の移動距離を考える。
C[i-1]番のロボが引き返した位置をX[i-1]とする。この時、i番のロボのタンクは満タンである。
ここからy進んだ位置で引き返すとすると、i番のロボがy進んで(C[i-1]+y)戻るために必要な燃料は(C[i-1]+2y)となる。
また、その時i+1番のロボはそこまでの(C[i-1]+y)進んだ分消費した燃料タンクを再度満タンにする必要がある。
よって、(X[i-1]+2y)+(X[i-1]+y) = C[i]であり、y=(C[i]-2*X[i-1])/3である。
そのためX[i]=X[i-1]+y=(C[i]+X[i-1])/3となる。
さらに変形すると、X[i]=sum(C[x]/(3^x))となる。

この式からも、先に引き返したロボほど、最終的にロボが進める位置への寄与が小さいので、容量が小さいロボを若い番号にした方が良いことがわかる。

ここまでわかると後はDPするだけである。
ロボを容量の小さい順にソートし、dp[ロボ番号][残り金額]=最大移動距離 でDPしていく。
dp[0][B]=0から始まり、dp[i+1][x-cost[i]]=cap[i]+dp[i][x]/3でdpしていってdp[N][x]/2の最大値が解。

pair<int,int> P[502];
double dp[2][10002];

class CtuRobots {
	public:
	double maxDist(int B, vector <int> cost, vector <int> cap) {
		int i,x,y;
		
		int N=cost.size();
		FOR(i,N) P[i]=make_pair(cap[i],cost[i]);
		sort(P,P+N);
		
		FOR(i,B+1) dp[0][i]=-1;
		double ma=0;
		dp[0][B]=0;
		FOR(i,N) {
			int cur=i%2,tar=cur^1;
			FOR(x,B+1) dp[tar][x]=-1;
			FOR(x,B+1) if(dp[cur][x]>=0) {
				dp[tar][x]=max(dp[tar][x],dp[cur][x]);
				if(x>=P[i].second) {
					dp[tar][x-P[i].second]=max(dp[tar][x-P[i].second],P[i].first+dp[cur][x]/3);
					ma=max(ma,dp[tar][x-P[i].second]);
				}
			}
		}
		
		return ma;
	}
}

まとめ

本番、移動距離の計算もDPの処理もどちらも迷ったが、何とか時間内に解ききれてよかった。