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