結果

問題 No.1413 Dynamic Sushi
コンテスト
ユーザー seiyu_kyopro
提出日時 2021-03-02 00:09:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 283 ms / 4,000 ms
コード長 2,599 bytes
コンパイル時間 1,835 ms
コンパイル使用メモリ 173,732 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-03 01:17:14
合計ジャッジ時間 8,087 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define rrep(i, n) for (int i = (int)n-1; i >= 0; --i)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const long double PI = 3.14159265358979;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;

template<typename T> bool chmin(T& a, const T& b) { return (b < a) ? (a = b, true) : false; }
template<typename T> bool chmax(T& a, const T& b) { return (a < b) ? (a = b, true) : false; }

const int max_n = 12;
const int max_x = 100;

int N;
double W;
double x[max_n + 1], y[max_n + 1], r[max_n + 1], v[max_n + 1], a[max_n + 1];

double calc_earliest_time(int from, int to, double t){
    double ng = 0, ok = double(600) / W;
    double ra_s = (v[from] * t + a[from]) * PI / 180;
    double sx = x[from] + r[from] * cos(ra_s);
    double sy = y[from] + r[from] * sin(ra_s);
    for (int i = 0; i < 30; i++){
        double mi = (ok + ng) / 2;
        double ra_g = (v[to] * (t + mi) + a[to]) * PI / 180;
        double gx = x[to] + r[to] * cos(ra_g);
        double gy = y[to] + r[to] * sin(ra_g);
        double dx = gx - sx;
        double dy = gy - sy;
        double dis = W * mi; // ルンルンの移動距離
        if(dx*dx + dy*dy < dis*dis){
            // 到達可能
            ok = mi;
        }else{
            ng = mi;
        }
    }
    // cout << lo << endl;
    // cout << t + lo << endl;
    // cout << "--------------------" << endl;
    return t + ok;
}

int main(){
    cin >> N >> W;
    for (int i = 0; i < N; i++){
        cin >> x[i] >> y[i] >> r[i] >> v[i] >> a[i];
    }

    vector<vector<double>> dp(1 << N, vector<double>(N + 1, inf));

    for (int mask = 0; mask < (1 << N); mask++){
        for (int i = 0; i < N + 1; i++){
            // 始点 -> 0
            // otherwise -> INF
            if (mask == 0 && i == N) dp[mask][i] = 0;
            else
                dp[mask][i] = INF;
        }
    }
    
    for (int mask = 0; mask < (1 << N) - 1; mask++){
        for (int i = 0; i < N + 1; i++){
            if(mask == 0 && i == N || mask>>i & 1){
                // 始点あるいは，頂点iを訪れたことがある.
                for (int j = 0; j < N; j++){
                    if(!(mask>>j & 1)){
                        chmin(dp[mask | 1 << j][j], calc_earliest_time(i, j, dp[mask][i]));
                    }
                }
                
            }
        }
    }

    double ans = inf;

    rep(j, N) chmin(ans, dp[(1 << N) - 1][j]);

    cout << ans << endl;

    return 0;
}
0