AOJ-ICPC 2016.10.10
問題
Network Reliability | Aizu Online Judge
問題概要
無向グラフが与えられる。
それぞれの辺は一定確率で消える。
グラフが連結である確率を求めよ。
解法
dp。
:= 頂点集合
が連結である確率 とする。
のとき
である。
のうちある頂点を
とし、
を
を含む
の部分集合、
をその補集合とする。
と
の間の辺の数を
とすると、
となる。
問題
Strange Couple | Aizu Online Judge
問題概要
重み付き無向グラフが与えられる。辺の重みは移動にかかる時間である。
頂点から頂点
に行く。
頂点には標識がある場合とない場合がある。
標識がある場合はTへの最短路となる辺に入る。
そのような辺が複数ある場合はその1つにランダムに入る。
標識がない場合はランダムな辺に入る。
かかる時間の期待値を求めよ。
解法
ガウスの消去法。
ある頂点から別の頂点に移動する確率と、その時間を漸化式にする。
全ての頂点についてそれを求め、１次方程式を解けばよい。
問題
Wind Passages | Aizu Online Judge
問題概要
細長い通路に複数の多角柱がおいてある。
風が通路を流れるとき、単位時間当たりに流れるを求めよ。
解法
どうみても最大流問題なので、最小カットを考えればよい。
解説スライドの図を見るとイメージしやすい。
左の壁から右の壁に多角形の中を通ることを許して移動するとき、多角形の外を移動する距離の最小値が答えになる。
つまり、壁および多角形間の距離を求めて、壁から壁への最短経路を求めればよい。
問題
Shadow Witch | Aizu Online Judge
問題概要
省略。
解法
「ゴールを飛び越える」は「跳ね返る」と考える。
ゴールまですごく遠いときはかなりの手数がかかりそうなので、ある程度近く(距離100000)ぐらいまでは期待値で移動できると考えてよさそう。
あとそこから後一手でゴールできるところまではDPで求める。
後一手でゴールできるところからは、漸化式がループするためDPできないので、一次方程式を解けばよい。
