結果

問題 No.463 魔法使いのすごろく🎲
コンテスト
ユーザー vjudge1
提出日時 2025-06-28 16:51:54
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.89.0)
結果
AC  
実行時間 235 ms / 2,000 ms
コード長 1,882 bytes
記録
コンパイル時間 7,741 ms
コンパイル使用メモリ 235,320 KB
実行使用メモリ 16,512 KB
最終ジャッジ日時 2025-06-28 16:52:05
合計ジャッジ時間 9,000 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;

void FileIO(){
    freopen("turnback.in","r",stdin);
    freopen("turnback.out","w",stdout);
}

namespace sunburstfan{
    #define int long long
    int n,m;
    vector<int> c;
    vector<vector<vector<double> > > f;
    vector<vector<vector<bool> > > vis;
    const int MAXTIME=1000;
    
    int get(int pos,int step){
        int next=pos+step;
        if(next>=n-1)next=2*(n-1)-next;
        return next;
    }
    
    double dfs(int time,int pos,int used_magic){
        if(pos==n-1||time>=MAXTIME)return 0.0;
        if(vis[time][pos][used_magic])return f[time][pos][used_magic];
        
        vis[time][pos][used_magic]=true;
        double res=1e18;
        
        double tmp=0.0;
        double P=1.0/m;
        for(int i=1;i<=m;i++){
            int next=get(pos,i);
            double cost=P*(c[next]+dfs(time+1,next,used_magic));
            tmp+=cost;
        }
        res=min(res,tmp);
        
        if(used_magic==0){
            for(int i=1;i<=m;i++){
                int next=get(pos,i);
                double cost=c[next]+dfs(time+1,next,1);
                res=min(res,cost);
            }
        }
        
        return f[time][pos][used_magic]=res;
    }

    void solve(){
        cin>>n>>m;
        c.resize(n);
        
        for(int i=1;i<=n-2;i++){
            cin>>c[i];
        }
        
        f.assign(MAXTIME+1,vector<vector<double> >(n,vector<double>(2,-1.0)));
        vis.assign(MAXTIME+1,vector<vector<bool> >(n,vector<bool>(2,false)));
        
        double ans=dfs(0,0,0);
        cout<<fixed<<setprecision(10)<<ans<<"\n";
        
        return;
    }
}
using namespace sunburstfan;
#undef int
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    //FileIO();

    int T=1;
    while(T--){
        solve();
    }
    
    return 0;
}
0