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: 2017年07月21日13時45分26秒
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)

ログイン: