roiti46's blog

主に競プロ問題の解説を載せてます

TopCoder Open Round 1B Medium: TheTips

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

問題はこちら

問題

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

解法

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

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

全体のオーダーはO(N3)。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

まとめ

落ち着いて考えれば解けただけにもったいない。 確率問題は苦手意識があるので練習が必要だなー。

広告を非表示にする