SRM543 Div1 Medium(500) EllysRivers

EllysRivers

普通に動的計画法をするとO(N²length)で間に合わない。終了間際になっても解けなかったので、自信は無かったけど、島iのj番目の港に最短時間で行くときに通る島i-1の港は、島iのj-1番目の港に最短時間で行くときに通る島i-1の港かその両隣、と仮定して書いたら通った。

歩きの移動はどこの島でも同じ速度なので、歩くのは最初の島のみとして良い。

#include <string>
#include <vector>
#include <cmath>
using namespace std;

class EllysRivers{public:
double getMin( int length, int walk, vector <int> width, vector <int> speed )
{
    int N = (int)width.size();
    
    vector<double> T(length+1);
    for ( int i=0; i<=length; i++ )
        T[i] = (double)i/walk;

    for ( int i=0; i<N; i++ )
    {
        vector<double> P = T;
        T = vector<double>(length+1,1e100);

        T[0] = P[0]+(double)width[i]/speed[i];
        int p = 0;

        for ( int j=0; j<=length; j++ )
        {
            int s = max(p-1,0);
            int e = min(p+1,j);

            for ( int k=s; k<=e; k++ )
            {
                double t = P[k]+hypot(width[i],j-k)/speed[i];
                if ( t < T[j] )
                {
                    T[j] = t;
                    p = k;
                }
            }
        }
    }

    return T[length];
}};

GeRichさんの解答が凄い。歩きでの移動を幅0の海と考える。それぞれの海で、width[i]の移動は常に必要。南北方向に1km移動距離が増えたときの時間の増加を、南北方向の距離ごとに計算して、その中から短い順にlength個の和を取る。例えば、3km→4kmを選ばずに4km→5kmを選んでしまったらマズいけど、距離が長いほど移動時間の増加は少ないので、そんなことはおこらない。

#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>
using namespace std;

class EllysRivers{public:
double getMin( int length, int walk, vector <int> width, vector <int> speed )
{
    width.push_back(0);
    speed.push_back(walk);

    int N = (int)width.size();

    double ans = 0;

    for ( int i=0; i<N; i++ )
        ans += (double)width[i]/speed[i];

    static double Q[51*100000];
    int q = 0;
    for ( int i=0; i<N; i++ )
        for ( int j=1; j<=length; j++ )
            Q[q++] = (hypot(width[i],j)-hypot(width[i],j-1))/speed[i];
    sort(Q,Q+q);
    ans += accumulate(Q,Q+length,0.0);

    return ans;
}};