ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Typical DP Contest C - トーナメント

問題
提出コード

解法

はじめに、P(x,y) = x番の人がy番の人に勝つ確率、としておきます。
dp[i][j] = i番目の人が、第jラウンドで勝つ確率、とします。
初期状態はdp[i][0] = 1であり、答えはdp[i][K]をすべて見ればよいです。
簡単に言えば、i番目の人が第jラウンドで戦う可能性のある相手の集合をSとしたときに、
\displaystyle dp[i][j] = dp[i][j-1] \times \sum_{l \in S}^{} \{P(i,l) \times dp[l][j-1] \}
となります。
さて、ここからはiが0-indexedであると仮定して話を進めたいと思います(その方が好都合だからです)。
Sに含まれる人を探していきます。第jラウンドでi番の人が対戦する可能性のある人は、全部で2^{j-1}人います。そして、その人達の番号はすべて連番になっています。
ということで、その連番の最初がわかってしまえば、そこから2^{j-1}人を対象として上の式による計算を行えばいいわけです。
第1ラウンドについて考えてみると、i番目の人は、iが奇数であればi-1番目の人と、iが偶数であればi+1の人とのみ対戦を行います(0-indexedにしたことに気を付けてください)。
第2ラウンドについて考えてみると、0,1番の人は2,3番の人と、4,5番の人は6,7番の人と対戦を行うことになります。
これを繰り返すと、
jラウンドでは、2^{j-1}人ごとにグループ分けをして、若い番号の人がいるグループから順番に0,1,2...と番号を振り、その後0と1、2と3…グループで対戦を行います。
なので、まずi2^{j-1}で割った値を求めます(これをxとします、切り捨てです)。すると、これがグループ番号となるので、あとはxが偶数ならx+1グループと、奇数ならx-1グループと対戦を行います。
そして、xグループの先頭は、x\times 2^{j-1}となります。そこから2^{j-1}人が、今回i番の人が対戦する可能性のある相手になります。
これにより、第jラウンドにおけるiの対戦相手がわかったので、あとは遷移の式にしたがって計算をしていけば、答えを求めることができます。