UVa542 France '98

問題文
http://uva.onlinejudge.org/external/5/542.html

問題概要
サッカーのトーナメント戦がある。a国がb国に勝つ確率が隣接行列で与えられるので、出場する16カ国それぞれについての優勝確率を算出せよ。

解法
1試合で a国が勝つパターンと b国が勝つパターンがあるので、両方考慮して2分木の再帰をする。
どのような意識で再帰システムを構築するか。ここで 1回の試合で2カ国が1カ国に絞られることに着目する。2つのうちのどちらか1つに絞るのだが、どちらも考える必要があるので、つまり絞るパターンA, パターンB とそれぞれを決めて再帰してやるということ。
具体的には、i*2 [i*2+1] 試合目の勝者国が i 試合目の勝者国となると言えば良い。
よって、試合の勝者国を決める winner[i] 配列を用意する。初期状態として、それぞれの国の勝利確率を 1.0 (このトーナメントの出場権みたいなもの) と試合番号を与え、1度の試合で勝利する国を定めながら N-1 試合分の再帰を試せば良い。winner[i] 配列は、要素を決勝戦(1-indexed)から、それに先行する試合に向けて試合番号を増加させていくと都合がいい。N 試合目から 2*N 試合目を各国の、勝利確率1.0 の出場権とみなすと、初期値を rep(i, N) winner[N+i] = i; とすれば初めの試合フェーズが隣ペアで行われる事象が達成され、その再帰で答えが求まる。