Logfiles

LiveArchive 5875 Orienteering

問題

巡回コースの通過点のリストが与えられる。 $N$ 個の通過点と $M$ 人のプレイヤーがいる。各通過点は $(x_i,\ y_i)$ 座標に存在し、得られる得点が $s_i$ である。各プレイヤーは名前 $name_i$ と移動できる最大距離 $d_i$ を持つ。各プレイヤーは原点から移動を始め、入力の通過点のうち幾つかの通過点の集合を選び、それを入力の順に訪れて、最後に原点に戻る。プレイヤーの移動は直線的で最短経路を辿る。プレイヤーの入力の順に、プレイヤー名と得られる最大得点を出力せよ。

解説

ナップザックDPとなる。距離が実数で引数に持てないため、整数である得点を引数にもつようにする。つまり、

$dp[最後にiを訪れた][価値v]\ :=\ 移動を達成するための最短距離$

として、

$dp[ 0 ][ 0 ]\ =\ 0$
$dp[ i ] [ v + s_i ]\ =\ max(dp[ i ] [ v + s_i ], dp[ j ] [ v ])\ (j\lt i)$

と計算する。場所0を原点と決めておくと良い。最後に、

$dp [ i ] [ v ] + \sqrt{x_i^2 + y_i^2} \le d_{player} + EPS$

を満たす最大の $v$ を求めれば良い。三平方の定理で斜辺を計算するときは、cmathのstd::hypotを使うのが楽。

int const MAX_V = 30;
int const MAX_S = MAX_V * 200;
 
int main() {
 
  for(int N, tc = 1; cin >> N && N; tc++) {
    vector<tuple<int, int, int>> vs;
    vs.emplace_back(0, 0, 0);
    for(int i=0; i<N; i++) {
      int x, y; int s; cin >> x >> y >> s;
      vs.emplace_back(x, y, s);
    }
 
    N++;
 
    static double dp[MAX_V][MAX_S + 1];
 
    for(int i=0; i<MAX_V; i++)
      for(int j=0; j<MAX_S + 1; j++)
        dp[i][j] = inf;
 
    dp[0][0] = 0;
 
    for(int i=0; i<N; i++) {
      int xi, yi, _; tie(xi, yi, _) = vs[i];
      for(int j=i+1; j<N; j++) {
        int xj, yj, s; tie(xj, yj, s) = vs[j];
        for(int value = 0; value <= MAX_S; value++) {
          if(dp[i][value] < inf)
            dp[j][value + s] = min(dp[j][value + s], dp[i][value] + hypot(xi - xj, yi - yj));
        }
      }
    }
 
    cout << "Race " << tc << endl;
 
    for(;;) {
      string s; int x; cin >> s >> x;
      if(s == "#") break;
 
      int maxi = 0;
      for(int i=0; i<N; i++) {
        int xi, yi, _; tie(xi, yi, _) = vs[i];
        for(int value = MAX_S; value >= 0; value--) {
          if(dp[i][value] < inf - EPS && dp[i][value] + hypot(xi, yi) <= x + EPS) {
            maxi = max(maxi, value);
          }
        }
      }
      cout << s << ": " << maxi << endl;
    }
  }
   
  return 0;
}