yukicoder No.66 輝け☆全国たこやき杯

問題

問題概要

トーナメントで勝ち進んでいく確率。

解法

dpで解いた。
dp[i][j] := i回回目の試合にj番目のひとが勝つ確率　として、漸化式にそって、ループで値を埋めていく。漸化式は簡単で、
dp[i + 1][x] += dp[i][x] * dp[i][y] * memo[x][y]
のようになる。これは、i回目まで、x番目の人と、y番目の人が勝ち上がっている確率に、x番目の人とy番目の人が戦った時に、x番目の人が勝つ確率をかけている。これをi+1番目にxさんが戦う可能性のある人全員に対して行い、それらの確率を合計することで、i+1番目の試合で、x番目の人が勝つ確率がわかる。
今回の問題で一番難しくてわからなかったのは、i番目の試合で、xさんがだれと戦う可能性があるかといことです。人と、試合の番号を0iindexで考えると、i番目の試合で戦うひとは、人の番号を2進数で表したときに、自分の番号のi桁目が対戦相手とは異なり、i桁目より左の桁はともに一致しており、i桁目より右の桁には特に制限はない。
ex)例えば、1試合目(0index)の時、自分が0(000)とすると、対戦相手の候補は2(010)と3(011)
まず、i桁目が異なることを調べるには、
(x xor y) & (1 << i)) != 0
を行えばいい。xとyの1桁目が異なるなら、x xor yでi桁目が1となるので、(1 << i)とandを取ることで、調べられる。
次に、i桁目より、左の桁が一致していていて、i桁目より左が任意であることを調べるには、 i桁目以下が0で行けた目より大きい桁が1である、mask = 11111100を使い、
(x & mask) == (y & mask)
を行えばいい。maskとandを取ることで、i桁目以下は必ず0になり、i桁目より大きい桁ではxのbitによってandの結果が変わるので、xとyが同じであれば、結果が一致するので調べられる。　　 maskは1で初期化しておきて、毎回i桁目から1を引くようにすればいい。

ミス

確率dpの練習を兼ねてやることにした。dpの添え字や漸化式は容易に方針を立てることができたが、トーナメントにおいて、何回目の試合で、何番目の人は、だれと戦うかのうせいがあるのかを判断する方法がわからなかった。kmjpさんの実装がきれいすぎた。

コード

確率dp

#include <iostream>
#include <cstdio>
#include <cmath>
typedef long long ll;
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

//dp[i][j] := i回回目の試合にj番目のひとが勝つ確率

double dp[12][1200];
int m;
double s[1200];
//memo[i][j] := iとjが戦い、i番目の人が勝つ確率
double memo[1200][1200];
int main(void){
    cin >> m;
    rep(i, pow(2, m)) cin >> s[i];
    rep(i, pow(2, m))rep(j, pow(2, m)){
        memo[i][j] = pow(s[i], 2.0) / (pow(s[i], 2.0) + pow(s[j], 2.0));
    }

    //確率dp　(可能性のある対戦相手を探すのが難しい)
    rep(i, 12)rep(j, 1200) dp[i][j] = 0.0;
    rep(i, 1200)dp[0][i] = 1.0;

    int mask = 0xFFFFFF;
    for (int i = 0; i < m; ++i){//何試合目
        mask -= 1 << i;
        for (int x = 0; x < (1 << m); ++x){//戦う人の番号(勝率を求める側)
            for (int y = 0; y < (1 << m); ++y){//i試合目に戦う可能性のある相手を探す
                if(x == y)continue;
                if(((x ^ y) & (1 << i)) != 0 && (x & mask) == (y & mask)){//ここが難しい
                    dp[i + 1][x] += dp[i][x] * dp[i][y] * memo[x][y];
                }
            }
        }
    }
    printf("%.9f\n", dp[m][0]);
    return 0;
}