水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

Typical DP Contest:C - トーナメント

問題

beta.atcoder.jp

解法

「dp(i, j) := 人 i が j 回戦目で勝つ確率」と DP を立てる.人 i と j 回戦目で当たる可能性がある人を人 l, l + 1, l + 2, ... , r とし,人 a が人 b に勝つ確率を p_(a, b) とすると,

dp(i, j) = dp(i, j - 1) * ( dp(l, j - 1) * p_(i, l) + dp(l + 1, j - 1) * p_(i, l + 1) + ... + dp(r, j - 1) * p_(i, r) )

と漸化式が立つ.あとは一人ずつ DP をすればよい.O(2^K^2 * K).

解答

beta.atcoder.jp

一発 AC だったのでよかった.

f:id:babcs2035:20181202144541p:plain