結果

問題 No.463 魔法使いのすごろく🎲
コンテスト
ユーザー vjudge1
提出日時 2025-06-28 16:43:19
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,824 bytes
コンパイル時間 6,878 ms
コンパイル使用メモリ 225,144 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-06-28 16:43:30
合計ジャッジ時間 8,537 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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<double> > f;
    vector<vector<bool> > vis;
    
    int get(int pos,int step){
        int next=pos+step;
        if(next>n){
            next=2*n-next;
        }
        return max(1ll,next);
    }
    
    double dfs(int pos,int lst){
        if(pos==n)return 0.0;
        if(vis[pos][lst])return f[pos][lst];
        
        vis[pos][lst]=1;
        double res=1e18;
        
        double tmp=0.0;
        for(int i=1;i<=m;i++){
            int next=get(pos,i);
            double cost=dfs(next,lst);

            if(next!=1&&next!=n){
                cost+=c[next];
            }

            tmp+=cost;
        }

        tmp/=m;
        res=min(res,tmp);
        
        if(lst==0){
            for(int i=1;i<=m;i++){
                int next=get(pos,i);
                double cost=dfs(next,1);

                if(next!=1&&next!=n){
                    cost+=c[next];
                }
                res=min(res,cost);
            }
        }
        
        return f[pos][lst]=res;
    }

    void solve(){
        cin>>n>>m;
        c.resize(n+1);
        
        for(int i=2;i<n;i++){
            cin>>c[i];
        }
        
        f.assign(n+1,vector<double>(2,0.0));
        vis.assign(n+1,vector<bool>(2,false));
        
        double ans=dfs(1,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