Journey [AtCoder Beginner Contest 194 D]

https://atcoder.jp/contests/abc194/tasks/abc194_d

前提知識

• 競技プログラミングにおける確率・期待値問題 - はまやんはまやんはまやん
  • 「有効なのが来るまでカードを引く期待値は、有効なカードを引く確率の逆数になる。」

解説

https://atcoder.jp/contests/abc194/submissions/20735452

これは正直知らないと一生迷う問題。
「有効なのが来るまでカードを引く期待値は、有効なカードを引く確率の逆数になる。」
これを知っているかどうか。

状態を圧縮して考える

ゴールは頂点1と連結している頂点の数がN個になること。
これを意識することでだいぶ状態を圧縮できる。

例えば頂点が5頂点あって、123は連結してるけど、45はそうじゃない場面を考える。
この時、123のどこにいたとしても連結数を1増やすには選択時に2/5の確率を引く必要がある。
全て同じ遷移条件であるため「どこにいるか」は抽象化していい条件となる。

次に123の連結と124の連結状態を考える。
これも連結数を1増やすには選択時に2/5の確率を引く必要がある。
全て同じ遷移条件であるため「どこと連結か」は抽象化していい条件となる。

つまり、状態は頂点1と連結している調点数がいくつかという部分だけを考えればよくなる

状態の遷移にかかる回数の期待値

すこし見通しをよくすると、状態の遷移は以下のようになる。
「（最初）連結数1」→「連結数2」→「連結数3」→…→「連結数N」
「連結数1」→「連結数2」の遷移を考えると、(N-1)/Nの確率を引くと次の状態に移り、そうでないなら同じ状態にとどまる。
この状態は「有効なのが来るまでカードを引く期待値は、有効なカードを引く確率の逆数になる。」と同じ状態になる。
よって、状態が遷移できる期待値はN/(N-1)となる。
この期待値がすべての状態遷移において発生するので以下のような実装でACできる。

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    double ans = 0;
    rep(grp, 1, N) ans += 1.0 * N / (N - grp);
    printf("%.9f\n", ans);
}