問題
n個の宝を探す宝探しゲームをする。ノーヒントで宝iを探せる確率はp[i]
G[i][j]=Yならばi番目の宝が見つかればi番目の宝にj番目の宝の場所も記されているのでj番目の宝も見つけられる。
見つけられる宝の個数の期待値を求める問題。
解法
i番目の宝が見つかる確率をp[i]とおく。
G'[i][j]を「iからjまで連結しているならば1」として隣接行列を作る。
この時p[i]は「1- (iに到達できるnodeがどれも見つからない)」なので余事象で簡単に計算できる。
登録:
コメントの投稿 (Atom)
-
概要 焼きなまし法 は遺伝的アルゴリズムなどと並ぶ最適化問題の発見的解法の一つとして有名であり, 競技プログラミングの文脈ではマラソン(厳密解を求めるのが困難とされる一つの最適化問題に長時間取り組み最も最適値に近い解を得るという種目) においては常套手段の一つとして用いられていま... -
競プロで道具として用いられる様々な賢いアルゴリズムやデータ構造の多くは, 非常に賢い研究者たちによって発見されており, ほとんどは理論計算機科学の論文として国際学会の会議録や学術雑誌の形として出版されています. ここではアルゴリズム系の研究論文がよく出てくる様々な国際会議を紹介し...
-
0. 背景 グラフ理論とは文字通り, グラフについて解析する分野です. グラフ理論のモチベーションとしては, 「最小全域木」「最大マッチング」「最大フロー」などのアルゴリズムを考える際に対象となるオブジェクト(この例で言えば全域木, マッチング, フロー)に対する「良い」...
0 件のコメント:
コメントを投稿