問題概要
量 F の燃料を積載した航空機があり、これを用いていくつかの「任務」をこなしたい。任務は複数個あり、i 番の任務を遂行するためには duration[ i ] の燃料が必要となり、任務終了後に refuel[ i ] の燃料が補充される。任務開始前に航空機に積載されている燃料量が duration[ i ] 未満のとき、その任務を遂行することはできない。また、任務には好きな順番で取り組むことができるが、各任務は高々一回しか実行できない。なお、全ての任務に関して refuel[ i ] < duration[ i ] である。
最大でいくつの任務を遂行することができるか、求めよ。
解法
任務の数を N と表記します。
任務に取り組む順番を全て試すと となってもちろん間に合いません。完了した任務と燃料の残量が同じ状態が複数あれば最良のものだけを残せば良いことを利用して DP にすると
となりますが、これでもまだ大きすぎます。更に計算量を減らす必要があります。
ここで、任務を適切に順序付けることができれば、ある時点での燃料残量を保持しつつ先頭から順に遂行するか否かを決めていく の DP が得られます。任務順序付けについては、複数の任務をこなすならば refuel が大きい物を先にこなした方が良さそうに思えます。この予想は正しく、正答を得られます。ここではこれを証明します。
順序付けの妥当性
適切な順序で取り組むことで共に遂行可能な二つの任務があり、それぞれの duration の値が d1, d2 、refuel の値が r1, r2 であるとします。また、任務開始前の残燃料量を f とします。このとき、( d1, f1 ) により特徴付けられている任務を先にこなすとすれば、燃料量は次のように変化します。
- f
- f - d1
- f - d1 + r1
- f - d1 + r1 - d2
- f - d1 + r1 - d2 + r2
このとき、1, 5 の値はどちらの任務を先にこなしても同一です。更に、制約より燃料量が常に f 以下となる点を踏まえると、仮定より d1, d2 <= f であると言えます。従って、2, 3 の状態で燃料量が 0 未満となることはないので、取り組む順序によって invalid となりうるのは 4 の時点だけです。4 の時点について、任務の順序を変えることで生じる変化は、加算される値が r1 か r2 かで変化するだけなので、refuel が大きい方を先に（ r1 となるように）こなした方が、より少ない燃料量から遂行可能であると分かります。すなわち、適切な順序でこなすことでのみ共に遂行可能な二つの任務があるとき、「適切な順序」とは refuel が大きいものを先になるような順序であると結論できます。また、順序付けに於いて後ろにいくほど refuel の値が小さくなるので、順序付けが循環してしまうこともありません。
解を求める
前節で示したように、refuel の値をキーにすることで任務を順序付けることができました。これなら先頭から順番に考慮することができるので、次のような DP を考えられます。
- dp[ i 個の任務について考慮した ][ 燃料残量が j ] := ここまでにこなせる任務の最大数
dp[ i ][ j ] からの状態遷移は i + 1 番目の任務をこなすかどうかを両方試すことになるので、
- dp[ i + 1 ][ j - duration[ i ] + refuel[ i ] ] を dp[ i ][ j ] + 1 で更新（ただし 0 <= j - duration[ i ] のときに限る）
- dp[ i + 1 ][ j ] を dp[ i ][ j ] で更新
の二通りです。計算が終わった後、dp[ N ] の最大値が問題に対する答えとなります。
コード
typedef vector<int> VI; typedef vector<VI> VVI; typedef pair<int,int> PII; typedef vector<PII> VPII; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define ALL( c ) (c).begin(), (c).end() #define MP( a, b ) make_pair( ( a ), ( b ) ) #define fst first #define snd second const int INF = INT_MAX / 4; class AlbertoTheAviator { public: int MaximumFlights( int F, vector <int> duration, vector <int> refuel ) { const int N = duration.size(); VPII missions; transform( ALL( duration ), refuel.begin(), back_inserter( missions ), []( int d, int r ){ return MP( d, r ); } ); sort( ALL( missions ), []( PII a, PII b ){ return a.snd > b.snd; } ); VVI dp( N + 1, VI( 5001, -INF ) ); dp[0][F] = 0; REP( i, 0, N ) { REP( j, 0, 5001 ) { if ( 0 <= j - missions[i].fst ) { int &next = dp[ i + 1 ][ j - missions[i].fst + missions[i].snd ]; next = max( next, dp[i][j] + 1 ); } { dp[ i + 1 ][j] = max( dp[ i + 1 ][j], dp[i][j] ); } } } return *max_element( ALL( dp.back() ) ); } };
