NJPC2017 F - ダブルス (解説を見た)

何もわからなかったので解説を見た。
F - ダブルス

問題

無限に伸びる数直線上に2人の人間が立っている。2人の初期位置は0である。この2人は協力して以下の条件を満たしたい:

  • 時刻0以降に散発的に光点が現れるので、2人のうちのどちらかがその光点を叩く。光点は合計N回現れ、i番目の光点は時刻T[i]のときに場所X[i]に現れる。2人は速度V以下で動くことができる。

この条件を満たせるようなVの最小値を求めよ。

制約

  • 1 <= N <= 10^5
  • 1 <= T[i] <= 10^9
  • -10^6 <= X[i] <= 10^6
  • T[i]は狭義単調増加

解法

Vについての二分探索で判定問題に変換する。(「速度V以下で条件を満たせるか?」という問題に変換できる。)
dp[i][j] = (2人がi, jにいることがあり得るかどうか)というDPでこの問題を解くことはできるが、O(N^2)時間かかる。
そこで、状態のうち一つを圧縮して、dp[i] = (i番目までの光点が現れ、一人がiにいる場合、その時もう一人が存在し得る範囲)とするとうまく行くことが証明できる。遷移は以下の通り(dp[i] = [l, r]とし、D = V(T[i + 1] - T[i])を、時刻T[i]からT[i+1]の間に2人が移動可能な距離とする):

  • iにいる人がi+1に行く場合、dp[i] <- [l - D, r + D]
  • iにいない方の人がi+1に行く場合、dp[i] <- [X[i] - D, X[i] + D]

どちらか一方しか実現しない場合はそちらの区間を、両方実現する場合は両方の区間のunionをdp[i + 1]とすればよい。(unionが実際に区間になることの証明は解説を参考にしてください)
遷移はO(1)なので、この問題はO(N * log(V))で解ける。

登場する典型

  • 二分探索で最大化問題を判定問題に変換する
  • bool値のDPの状態の一つを値に持って行く

実装上の注意点

  • 2分探索のループ回数に気をつける
    • 時間に余裕があるので100回くらいやればよい
  • 最初時刻0のとき位置0にいる
    • 番兵などを使うと実装しやすい


提出: Submission #4272588 - NJPC2017 (C++)

// This solution is made after the author read the editorial.
bool ok(int n, const vector<double> &t, const vector<double> &x, double v) {
  vector<pair<double, double> > dp(n + 1);
  const double INF = 1e18;
  dp[0] = make_pair(0.0, 0.0);
  REP(i, 0, n) {
    double dist = v * (t[i + 1] - t[i]);
    dp[i + 1] = make_pair(INF, -INF);
    if (abs(x[i + 1] - x[i]) <= dist) {
      dp[i + 1].first = min(dp[i + 1].first, dp[i].first - dist);
      dp[i + 1].second = max(dp[i + 1].second, dp[i].second + dist);
    }
    if (dp[i].first - dist <= x[i + 1] && x[i + 1] <= dp[i].second + dist) {
      dp[i + 1].first = min(dp[i + 1].first, x[i] - dist);
      dp[i + 1].second = max(dp[i + 1].second, x[i] + dist);
    }
    if (dp[i + 1].first > dp[i + 1].second) return false;
  }
  return true;
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<double> t(n + 1), x(n + 1);
  REP(i, 0, n) cin >> t[i + 1] >> x[i + 1];
  double pass = 1e7, fail = 0;
  REP(i, 0, 100) {
    double mid = (pass + fail) / 2;
    if (ok(n, t, x, mid)) {
      pass = mid;
    } else {
      fail = mid;
    }
  }
  cout << setprecision(15) << pass << endl;
}

まとめ

最初実家DP + CHTかなと思ったが、CHTは大嘘で、ちゃんと問題の性質を調べる必要がある問題だった…。