TopCoder Open Round 1B Medium: TheTips

本番は答えられず。Div2Medよりちょっと難しいくらいか。

問題

あなたはTipsと呼ばれるゲームをしていて、N(≦ 50)個あるclueをいくつ見つけられるか遊んでいる。i番目のclueはP_i％の確率で見つけることができ、そのclueを見つけられるとほかのclueのうちいくつかを見つけることができる。あるclueを探せるのは一度だけとする。すべてのclueを探した時、見つけられるclueの数の期待値を答えよ。

解法

あるclueが最後まで見つからない確率を考えていく。あるclueが最後まで見つからないのは、直接探しても見つからず、またあるclueにつながるほかのclueや、もしくは間接的にあるclueにつながるほかのclueすべてが見つからない場合にのみである。あるclueが見つかることにつながるすべての確率P_jについて (1.0 - P_j) を乗じたものを P とすると、あるclueが見つかる確率は 1.0 - P となる。これを足し合わせれば答えとなる。

あるclueが見つかると結果的にどのclueが見つかるかどうかはワーシャルフロイドで求めることができる。

全体のオーダーはO(N³)。Nが小さいのでLL系の言語でも余裕で間に合う。

def solve(self, clues, probability):
    n = len(clues)
    clues = [[1 if clues[i][j] == "Y" else 0 for j in xrange(n)] for i in xrange(n)]
    for k in xrange(n):
        for i in xrange(n):
            for j in xrange(n):
                if i == j or j == k or k == i: continue
                clues[i][j] |= clues[i][k] & clues[k][j]
                
    prob = [p / 100.0 for p in probability]
    ans = 0.0
    for i in xrange(n):
        tmp = 1.0
        for j in xrange(n):
            if i != j and not clues[j][i]: continue
            tmp *= 1.0 - prob[j]
        ans += 1.0 - tmp
    return ans