Typical DP Contest: C トーナメント - Senの競技プログラミング備忘録

tdpc.contest.atcoder.jp

概要

$2^K$ 人のレーティングはそれぞれ設定されていて、人 i が人 j に勝つ確率は $\frac{1}{1+10^{\frac{R_j - R_i}{400}}}$ 。
人1, 2, 3, 4, ..., 2^Kの順に並び、それぞれ平衡二分木になるようなトーナメントを組む(詳細は問題文参照)。
人1, 2, 3, 4, ..., 2^Kの順に優勝する確率を答えよ。

ACするまで

1. dp[i][j] := i回目(0-idx)の試合後で人j(0-idx)が残る確率　として遷移を考える。
2. 人jが対戦できるする可能性のある人を考える。そしてつめが甘かった。->確率の和が1を超える！

3. しっかり考えるとAC

考察

i回目の試合後に人jが生き残る確率は、対戦する可能性のあるすべての人と対戦して勝つパターンの確率の合計。
対戦する可能性のある人は、i回目の試合後として、
$[(j / 2^i) * 2^i, (j / 2^i + 1)*2^i)$ の範囲の人で、
$[(j / 2^{i-1})*2^{i-1}, (j / 2^{i-1}+1)*2^{i-1})$ の人でない人たち(なぜならば、i-1回の試合まででこれらの人は人jかそれ以外の人に負けてるからである)

例えば、16人いるとして、人4の2回目の対戦での相手として可能性があるのは
$[4/{2^2}*2^2, (4/{2^2}+1)/2^2)$ -> $[4, 8)$ -> 人4, 5, 6, 7で、そのうち1回戦までにかならず敗れてる相手は、
$[4/{2^1}*2^1, (4/{2^1}+1)*2^1)$ -> $[4, 6)$ -> 人4, 5である。

この時、実装時は上記のような式を書いてもよいが、シフト演算を使用すれば、

int l = (j << i) >> i, r = ((j << i) + 1) >> i;
//[l, r)の範囲内から次のものを除く
int el = (j << (i - 1)) >> (i - 1), er = ((j << (i - 1)) + 1) >> (i - 1);
//[el, er)の範囲にあるものは、i回目の試合より前で負けてるので対戦することはない。

ACコード：
Submission #8325338 - Typical DP Contest | AtCoder

一言

モデリング力は経験値だなぁー。後日復習必須