D - AtCoder Express メモ

※texにキーワードリンクが張られて数式が認識されない場合があるため見づらくなってます。脳内補間おなしゃっす

問題

D - AtCoder Express

考えたこと

便宜のためを区間と書きます。

区間速度の修正

区間 の速度が [tex:v{i+1}] なので、区間 で出しても良い速度は [tex: \min( v {i+1}+t_i,v_i )]となります (区間 で [tex: v{i+1}+t{i}] より速かったら区間 で [tex:v{i+1}] より速くなります)。 [tex:v{N+1}]を0として最終区間からを更新していきます。

[tex:v{i+1}+t_i]より速いと区間で[tex:v{i+1}]を超える

場合分け

区間開始時の速度、区間の速度、次の区間の速度に応じて場合分けが必要です。

• の場合

区間の速度まで頑張ります

に到達する場合、しない場合

面積の計算は

Vr = Min(Vl + t, Vi[i]);//区間i終了時の速度
Adt = Vr - Vl;//加速時間。Vlは区間i開始時の速度
Cst = t - Adt;//v_iで走る時間
men = (Vl + Vr) * Adt / 2.0 + Cst * Vr;//面積

• の場合

区間終了時に以下になるように調整します。

に到達後減速、到達せずに減速

より早くならない場合減速の必要はなく加速のみです

加速のみ

面積の計算は

Vr = Min(Vi[i + 1], Vl + t);
Vm = Vi[i];//区間iの最大速度。とりあえずv_iとする
Adt = Vm - Vl;
Dst = Vm - Vr;//減速時間
if (t < Adt + Dst)//v_iに到達しない場合
{
    //Vl+Adt'=Dst'+Vr、Adt'+Dst'=t
    Adt = (t + Vr - Vl) / 2.0;
    Dst = t - Adt;
    Vm = Vl + Adt;
}
men = (Vl + Vm) * Adt / 2.0 + Vm * (t - Adt - Dst) + (Vm + Vr) * Dst / 2.0;

コード

static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
static void Main(string[] args)
{
    SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
    Solve();
    Out.Flush();
    Read();
}
static void Solve()
{
    var N = Sarray()[0];
    var Ti = Sarray();
    var Vi = Sarray();
    Vi = Vi.Concat(new long[] { 0 }).ToArray();
    for (var i = N - 1; 0 <= i; --i)
        Vi[i] = Min(Vi[i], Vi[i + 1] + Ti[i]);

    double Vl = 0, Vr = 0, sum = 0;
    for (var i = 0; i < N; ++i)
    {
        double men = 0;
        var t = Ti[i];
        if (Vi[i] + 0.1 < Vl) throw new Exception();
        if (Vi[i] <= Vi[i + 1])
        {
            Vr = Min(Vl + t, Vi[i]);
            var Adt = Vr - Vl;
            var Cst = t - Adt;
            men = (Vl + Vr) * Adt / 2.0 + Cst * Vr;
        }
        else
        {
            Vr = Min(Vi[i + 1], Vl + t);
            double Vm = Vi[i];
            double Adt = Vm - Vl;
            double Dst = Vm - Vr;
            if (t < Adt + Dst)
            {
                Adt = (t + Vr - Vl) / 2.0;
                Dst = t - Adt;
                Vm = Vl + Adt;
            }
            men = (Vl + Vm) * Adt / 2.0 + Vm * (t - Adt - Dst) + (Vm + Vr) * Dst / 2.0;
        }
        Vl = Vr;
        sum += men;
    }
    WriteLine($"{sum:f5}");
}

背景

結構いい感じの方法*1なのに場合分けでやってる人少ないっぽい？のでメモ。

*1:要出典