UVa 13030 - Brain Fry

Source

An Asian Preliminary Regional（20151205）
(ICPC Dhaka 2015 Preliminary)
UVa 13030

問題概要

ICPCのジャッジ団が人気商品を食べにレストランに行く．
ICPCの本部の大学はノード $0$ であり，レストランは $N$ 個あり，ノード $1$ から $N$ に割り振られている．
また，枝 $M$ 個が与えられ，つながっているノード間を双方向に移動でき，枝 $i$ を移動するのにかかる時間は $W_i$ である．
同じノード間には高々 $1$ 個の枝しかない．
また，ノード $i$ のレストランにおいて，その人気商品が食べられる確率 $P_i$ が与えられる，
それは，何回訪れようと，独立に，同じ確率 $P_i$ で人気商品が食べられる．
ジャッジ団は，制限時間 $T$ を決めた後，以下のアルゴリズムによって，レストランを訪ねて行く．

  1. すでに時間 $T$ 以上経過しているなら終了する．そうでなければ，ノード $0$ と隣接しているレストランを $1$ つ一様ランダムに選び，そのレストランに移動し（$1$ 個の枝を通って移動）ステップ [2.]へ．もし，隣接するレストランがないなら終了する．
  2. レストランに到着したら，人気商品が食べられるかどうか調べる．食べられるなら一瞬で食べて，最短距離でノード $0$ に戻って終了する．食べられないなら次のステップ [3.] へ．
  3. 時間が $T$ 以上経過しているなら，最短距離でノード $0$ に戻って終了する．そうでなければ，次のステップ [4.] に移動する．
  4. 現在の場所から隣接するレストランを $1$ つ一様ランダムに選び移動し（$1$ 個の枝を通って移動）ステップ [2.] へ．もし，隣接するレストランがないなら，最短距離でノード $0$ に戻り，ステップ [1.] に戻る．

人気商品を食べられる確率と，終了してノード $0$ に帰るまでにかかる時間の期待値を求める問題．

解法

動的計画法で，状態を（現在時刻，今いる場所）として，その確率を計算していく．
制約から推測される通り，枝は自己ループがありうるので注意．
ノード $0$ からの最短距離は最初に $1$ 回ダイクストラして計算しておく．
時間計算量は $O(T(N+M)+M \log N))$ 程度で，ダイクストラの代わりにワーシャルフロイドして $O(T(N+M)+N^3)$ でも十分通る．

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります．

Current time: 2024年04月17日02時07分56秒
Last modified: 2015年12月16日01時19分04秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151205_1
トップページに戻る

Logged in as: unknown user (not login)

ログイン：