AtCoder Typical DP Contest C トーナメント : Grenache's blog

問題概要

問題文はこちらを参照してください。

解法

優勝するには$K$連勝するということになるので、人$i$が$j$連勝する確率を考えます。これは$j-1$連勝する確率がわかっているとすると、その確率に$j$ラウンド目で勝つ確率をかければ求められます。

$j$ラウンド目で勝つ確率は、そこで当たる可能性がある人に勝つ確率の和、つまり自分が勝ち上がってきたトーナメントの山側ではない人$k$が$j-1$連勝して、かつ、その人に勝つ確率の和となります。

漸化式の定義： $$dp[i][j]=dp[i][j-1]\sum_{k\in S}dp[k][j-1]\cdot \Pr\{人iが人kに勝つ\}$$

$dp[i][j]$：人$i$が$K$連勝する確率
$(0\le i \le 2^K-1,\ 0\le j \le K,\ S=\{$人$i$が$j$ラウンド目で当たる可能性のある人$\})$

初期値：$dp[i][0]=1$

求める解：$dp[i][K]$

ここで、集合$S$は下記の図のように、自分が勝ち上がってきたトーナメントの山の人ではなく、$j$ラウンド目で当たる可能性のある人なので、$i$の下位$j-1$ビット以外の部分が一致せず、$i$の下位$j$ビット以外の部分が一致する人$k$となる(ただし、問題と違って$i$,$k$を0-indexedと考えた場合)。$k$は、mask=0xffffffff$<<$(j-1), mask2=0xffffffff$<<$jとしたときに、(i$\&$mask)$\ne$(k$\&$mask)かつ(i$\&$mask2)$=$(k$\&$mask2)を満たす。