E - 車の乗り継ぎ

Quiz

https://atcoder.jp/contests/gigacode-2019/tasks/gigacode_2019_e

AC

https://atcoder.jp/contests/gigacode-2019/submissions/8639311

サンプル6

解法

// i番目の車で j まで行く最短時間
double dp[2050][2050];

• と定義してDP
• 始点と終点にも車を定義して、車の位置の昇順でソートした、長さN+2の配列にて、

    // DP
    rep(i, 2050){
      rep(j, 2050){
        dp[i][j] = inf;
      }
    }
    // 0番目について
    FOR(i, 0, N+2){
      // iまで行けるか
      ll d = C[i].x;
      if(C[0].d >= d){
        // 行ける
        double t = (double)d / C[0].v;
        dp[0][i] = t;
      }
    }

    // i番目の車で行けるところまで行く
    FOR(i, 1, N+1){
      // i番目の車までに到達する最短時刻
      double until = inf;
      rep(j, N){
        chmin(until, dp[j][i]);
      }
      
      FOR(j, i, N+2){
        // i to jまで行ける？
        ll d = C[j].x - C[i].x;
        if(C[i].d >= d){
          // 行ける
          double t = (double)d/C[i].v;
          chmin(dp[i][j], t+until);
        }
        else{
          // 行けない
          break;
        }
      }
    }

    cout << setprecision(20);
    double ans = inf;
    rep(i, N+1){
      chmin(ans, dp[i][N+1]);
    }
    p(ans);

その他：公式解説はないのかな？

• https://atcoder.jp/contests/gigacode-2019
• GigaCode 2019、解説はないのかな？解説があると、後から見た人が精進に使えるので、資産になる

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?