結果

問題 No.1413 Dynamic Sushi
ユーザー seiyu_kyoproseiyu_kyopro
提出日時 2021-03-02 20:21:38
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 270 ms / 4,000 ms
コード長 2,067 bytes
コンパイル時間 1,695 ms
コンパイル使用メモリ 171,876 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-03 02:05:14
合計ジャッジ時間 7,740 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 237 ms
6,816 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 242 ms
6,820 KB
testcase_05 AC 249 ms
6,820 KB
testcase_06 AC 257 ms
6,816 KB
testcase_07 AC 261 ms
6,816 KB
testcase_08 AC 247 ms
6,816 KB
testcase_09 AC 262 ms
6,820 KB
testcase_10 AC 254 ms
6,816 KB
testcase_11 AC 256 ms
6,820 KB
testcase_12 AC 261 ms
6,820 KB
testcase_13 AC 263 ms
6,820 KB
testcase_14 AC 266 ms
6,816 KB
testcase_15 AC 260 ms
6,820 KB
testcase_16 AC 261 ms
6,816 KB
testcase_17 AC 267 ms
6,816 KB
testcase_18 AC 270 ms
6,820 KB
testcase_19 AC 254 ms
6,816 KB
testcase_20 AC 110 ms
6,816 KB
testcase_21 AC 3 ms
6,816 KB
testcase_22 AC 264 ms
6,820 KB
testcase_23 AC 265 ms
6,816 KB
testcase_24 AC 259 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

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) - 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;

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

    cout << ans << endl;

    return 0;
}
0