JAG 夏合宿 2010 3日目 B - Carrot Tour

Carrot Tour | Aizu Online Judge

問題概要

合計移動距離がr以下(0 < r < $ 10^4$)になるように20個以下の都市を回る． 都市を訪れる回数を最大化せよ． ただし，進む向きを一度に$ \theta$度より大きく変えることはできない．

解法概要

都市が20個以下という制約に反応してbitDPを書きたくなるが，これはbitDPでないDP (見事に引っかかってしまった) ．

dp[訪れた都市の数][1個前の都市][今の都市]の配列を埋めていけば良い．訪れることのできる都市の数はたかだか$ 10^4$個なので，都市の数をnとして(都市だけに……) $ O( \lfloor r \rfloor n^3)$のDPを書いても間に合う．都市間の距離や，曲がることができるかどうかは事前計算しておけば良い．

配列の初期化ミスに注意 (私は配列の初期化で何重にもミスを重ね，この問題に半日かけた) ．

ソースコード

#include<iostream>
#include<utility>
#include<cmath>
#include<algorithm>
#include<climits>
#include<complex>

#define debug(x) cerr << #x << ": " << x << endl
#define EPS 1e-5
#define MAX_R 200000.0
 
using namespace std;

int main(){
    int n;
    double r, theta;
    cin >> n;
    cin >> r >> theta;
    theta = theta/180.0*M_PI;
    complex<double> cities[n];
    for(int i=0;i<n;i++){
        double x,y;
        cin >> x >> y;
        cities[i] = complex<double>(x, y);
    }
 
    bool ok[n][n][n];
    fill_n(**ok, n*n*n, false);
    double dist[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i == j) continue;
            complex<double> v = cities[j] - cities[i];
            dist[i][j] = abs(v);
            for(int k=0;k<n;k++){
                if(i == k || j == k) continue;
                complex<double> u = cities[k] - cities[j];
                double theta_ = abs(arg(u/v));
                // theta_ = min(abs(arg(u) - arg(v)), 2*M_PI-abs(arg(u) - arg(v)))でも同じ
                if(theta_ < theta+EPS){
                    ok[i][j][k] = true;
                }
            }
        }
    }

    double dp[2][n][n];
    fill(dp[0][0], dp[0][n], MAX_R);
    for(int j=1;j<n;j++){
        dp[0][0][j] = dist[0][j];
    }
    int i = 0, ans = 0;
    for(int i=0;i<=10000;i++){
        fill(dp[1-(i&1)][0], dp[1-(i&1)][n], MAX_R);
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                if(j == k || dp[i&1][j][k] > r+EPS) continue;
                for(int l=0;l<n;l++){
                    if(j == l || k == l) continue;
                    if(ok[j][k][l]){
                        dp[1-(i&1)][k][l] = min(dp[1-(i&1)][k][l], dp[i&1][j][k] + dist[k][l]);
                    } 
                }
                ans = i+1;
            }
        }
    }
 
    cout << ans << endl;
}

所感

達成感はあるがとっても疲れた． 明日提出のレポートどうするの (知るか)