TDPC C - トーナメント

考え方

ABCでいうと、易しめのE問題級。

とはいえ、素直な方針でほぼ通る。
トーナメントの山ごとに、誰が勝ち残る確率がどの程度かを、下から順に求めていけばいいだけである。
ただし、全ての試合で全 $2^K$ 人分の確率を持つと、計算量が厳しい。
試合 $1$ 回ごとに $2^K\times 2^K$ 回の計算が必要で、それを $2^K-1$ 試合やるので、$O(2^{3K})$。
小数計算になるのもあって、$K=10$ の場合には流石の C++ でもちょっと厳しい。

そこで、少しだけ工夫。
その山にいない人がその山から上がってくる確率は $0$ である。
よって、各人が $i$ 回戦を勝ち上がる確率データは、長さ $2^K$ で持たなくても、長さ $2^i$ でいい。

そうすることで、$i$ 回戦目は $2^{i-1}\times 2^{i-1}$ 回の計算を $2^{K-i}$ 試合分やればよくなる。
つまり、$i$ 回戦目の計算量は $O(2^{K+i})$ となり、全体では $O(4^K)$ となる。

データの持ち方は、segment木のように $2$ 個ずつ合体する木でもいいし、deque などを用いてもよい。
ものによっては、DPテーブルと呼ぶのに多少違和感がある姿にはなるが……。

入力例2での動作

入力を受け取る。

k: 3
r: {2000, 2500, 2300, 2700, 2100, 2400, 2600, 2200}

最初は各選手 $1$ 人だけの山を作り、その山から勝ち上がる確率を $1$ とする。
隣り合う山を順に統合していく。

例えば、第 $1$ ラウンド第 $1$ 試合。
人 $1$ が人 $2$ に勝つ確率は、$\frac{1}{1+10^{(2500-2000)/400}}=0.053240\ldots$ である。
よって、この山のデータは、人 $1$ から順に $\{0.053240\ldots,0.946760\ldots\}$ となる。

同様に、あと $3$ 回分、$1$ 回戦を行う。

そして、第 $2$ ラウンド第 $1$ 試合。
片方の山は、人 $1$ から順に $\{0.053240\ldots,0.946760\ldots\}$ という山。
片方の山は、人 $3$ から順に $\{0.090909\ldots,0.909091\ldots\}$ という山。

ここから、それぞれの人がこの山を勝ち上がる確率を求める。

この山のデータは、人 $1$ から順に $\{0.001576\ldots,0.272174\ldots,0.024788\ldots,0.701462\ldots\}$ となる。

同様に決勝まで各山を統合すると、各選手がそれぞれのラウンドを勝ち上がる確率は次のようになる。

最後の列にあたる値を上から順に出力すればよい。

注意点

特になし。

別解

特になし。