問題概要
何体かのロボットが売られていて， 番のロボットの価格は
，燃料タンクの容量は
である．購入時に燃料タンクは満タンの状態になっている．これらのロボットの内いくつかを，予算
で購入する．購入後，購入したロボットに，連続した番号を任意に振る．
その後，ロボットを一斉に同じ速さで真っ直ぐ歩かせる．このとき，距離 1 進むために燃料を 1 消費する．ロボットは．割り振られた番号に従う順序で U ターンしてスタート位置に戻り始める．このとき，番号順で次のロボットに燃料を譲渡することができる．ただし，燃料タンクの容量を超えて譲渡することはできず，譲渡した方のロボットはスタート位置まで戻れるだけの燃料を残さなければならない．また，U ターンする位置の座標は整数に限らない．
あるロボットが到達できる位置の，スタート位置からの距離の最大値を求めよ．
解法
まずは燃料の譲渡について考えます．往路で使う燃料の量を ，復路に使う燃料の量を
，譲渡する燃料の量を
とします．往路と復路の距離が等しいことから，
です．また，譲渡位置までに消費した燃料以上の燃料を譲渡できないことから，
となり，まとめると
となります．この条件下で
を最大化すると考えると，
となることが分かります．つまり，段階が進むに従って，各ロボットの燃料が 1/3 ずつ次のロボットに移っていきます．別の言い方をすると，あるロボットからの譲渡で，次のロボットが使える燃料が，譲渡元のロボットのが使える量の 1/3 だけ増加します．
ところで，過去になされたあるロボットの譲渡による寄与は，段階が進む毎に 1/3 になっていきます．このことを利用して，ロボットの順序付けについて考えることができます．タンク容量が である 2 体のロボットがいて，この順で燃料を譲渡するとき，この 2 体に続くロボットの燃料の増加分は
です．このとき，
であったとすれば，
と
を交換することで値を大きくできます．任意のロボットの対について同じことが言えるので，ロボットの最適な順序付けはタンク容量の昇順と一致ことが分かります．
さて，譲渡により受け渡される燃料の量と，使うべき順序が分かりました．ということは，この順序に従って，先頭のロボットから順に買うか，買わないかを試していくことができるようになります．普通にやると状態数が多すぎるので，考慮した数と残り予算が同じ状態は同一視できることを使って，次のような動的計画法を考えます
- dp[ i 体考慮した ][ 合計金額が j ] := 往路に使える燃料
一番最後のロボットだけ譲渡が無いことを考えると，更にパラメータを一つ増やして
- dp[ i 体考慮した ][ 合計金額が j ][ 最後のロボットか否かを表す bool 値 ] := 往路に使える燃料
とすると一回の DP で全てを計算できます．dp[ i ][ j ] からの遷移は，次の 3 通りです
番目のロボットを使わない -> dp[ i + 1 ][ j ][ 0 ] を dp[ i ][ j ][ 0 ] との max で更新
以上の DP が終わったあと，dp[ i ][ j ][ 1 ] の最大値が問題の答えです．
コード
using PII = pair< int, int >; using VPII = vector< PII >; #define REP( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) #define ALL( c ) ( c ).begin(), ( c ).end() #define AALL( a, t ) ( t* )a, ( t* )a + sizeof( a ) / sizeof( t ) #define SZ( v ) ( (int)( v ).size() ) #define BI back_inserter #define MP make_pair #define fst first #define snd second double dp[ 512 ][ 10240 ][2]; class CtuRobots { public: double maxDist( int B, vector <int> cost, vector <int> cap ) { { // initialize for local fill( AALL( dp, double ), 0 ); } const int N = SZ( cost ); VPII ps; transform( ALL( cost ), cap.begin(), BI( ps ), []( const int a, const int b ){ return MP( a, b ); } ); sort( ALL( ps ), []( const PII &a, const PII &b ){ return a.snd != b.snd ? a.snd < b.snd : a.fst < b.fst; } ); REP( i, 0, N ) { REP( j, 0, B + 1 ) { { // not use dp[ i + 1 ][j][0] = max( dp[ i + 1 ][j][0], dp[i][j][0] ); } if ( j + ps[i].fst <= B ) { // use { double &next = dp[ i + 1 ][ j + ps[i].fst ][0]; next = max( next, ( dp[i][j][0] + ps[i].snd ) / 3 ); } { double &next = dp[ i + 1 ][ j + ps[i].fst ][1]; next = max( next, ( dp[i][j][0] + ps[i].snd ) / 2 ); } } } } double res = 0; REP( i, 0, N + 1 ) { REP( j, 0, B + 1 ) { res = max( res, dp[i][j][1] ); } } return res; } };
