結果

問題 No.1413 Dynamic Sushi
コンテスト
ユーザー seiyu_kyopro
提出日時 2021-03-02 21:11:16
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 275 ms / 4,000 ms
コード長 2,128 bytes
コンパイル時間 1,754 ms
コンパイル使用メモリ 172,464 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-03 02:08:46
合計ジャッジ時間 7,918 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
const double PI = 3.14159265358979;
const int inf = 1e9;
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;
        }
    }
    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));

    // 始点 -> 0
    dp[0][N] = 0;
    
    for (int mask = 0; mask < (1 << N); 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)){
                        // 頂点jを訪れたことがない．
                        chmin(dp[mask | 1 << j][j], calc_earliest_time(i, j, dp[mask][i]));
                    }
                }
                
            }
        }
    }

    double ans = inf;

    for (int j = 0; j < N; j++){
        chmin(ans, dp[(1 << N) - 1][j]);
    }

    cout << ans << endl;

    return 0;
}
0