TopCoder SRM 610 Div1 Medium AlbertoTheAviator

適当に書いたら通ってしまった問題。
http://community.topcoder.com/stat?c=problem_statement&pm=13024

問題

N個のフライトがある。
各フライトでは、duration[i]分燃料を消費し、帰ってくるとrefuel[i]分燃料を回復できる。
もちろんフライトに出かけるにはduration[i]以上燃料がなければならない。

初期状態として燃料がFあり、任意の順番でフライトできる場合、最大で何回フライトできるか答えよ。

解法

フライトの順番が決められないとうまく計算量を落とせない。
ちなみに答えはrefuel[i]が大きい順に飛ぶのが最適である。

よってrefuel[i]が降順となるようソートし、フライト回数Pを降順で総当たりして初期燃料FでP回フライトできるか、残り燃料を最大化するDPを行えばよい。

さて、問題はなぜrefuel[i]降順が良いかである。
これは自力では証明を思いつかなかったのでForumを参照した。

燃料Fのとき、フライトa→bの順で飛ぶには、bの時の燃料についてF-duration[a]+refuel[a]>=duration[b]でなければならない。
b→aの順なら逆にF-duration[b]+refuel[b]>=duration[a]である。

それぞれを変形すると

• F-duration[a]-duration[b]+refuel[a]>=0
• F-duration[a]-duration[b]+refuel[b]>=0

つまり、refuel[a]＞refuel[b]なら前者の方が成立しやすく、refuel[a]＜refuel[b]なら後者の方が成立しやすい。
よってrefuelの大きい順に飛ぶのが最適である。

int dpdp[51][51];
pair<int,int> P[51];

class AlbertoTheAviator {
	public:
	int MaximumFlights(int F, vector <int> duration, vector <int> refuel) {
		int N=refuel.size();
		int i,j,x,y;
		FOR(i,N) P[i]=make_pair(refuel[i],duration[i]);
		sort(P,P+N);
		reverse(P,P+N);
		
		for(i=N;i>0;i--) {
			ZERO(dpdp);
			dpdp[0][0]=F;
			FOR(j,N) {
				FOR(x,N) {
					if(dpdp[j][x]>=P[j].second) {
						if(x+1==i) return i;
						dpdp[j+1][x+1]=max(dpdp[j+1][x+1],dpdp[j][x]-P[j].second+P[j].first);
					}
					dpdp[j+1][x]=max(dpdp[j+1][x],dpdp[j][x]);
				}
			}
		}
		return 0;
	}
};

まとめ

こういう順番が問題文から自明に思いつかない場合、まずは２つの処理順を考えていくといいのね。
似たようなアプローチの問題は何回かやったことあるはずなのに、ぱっとこの考えに至れなかった。