microbeのブログ

進捗ダメです

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

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

 

問題概要

2^{k} 人でトーナメントが行われるのでそれぞれが優勝する確率を求める.
ただし,PとQが対戦してPが勝つ確率は1/(1+10^{(RQ-RP)/400})とする.

 

方針

確率DP
dp[i][j] := i回戦目でjが勝つ確率
PとQが対戦するかどうかの判定が難しかった...

 

ソース

gist19a47ee2cc462ea31dac94d13fe0f2cb