Typical DP Contest：C - トーナメント
問題
解法
「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)．
解答
一発 AC だったのでよかった．
