ABC194 D - Journey

AtCoder Python3 確率 期待値

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import datetime

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def it(): return tuple(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()

    ret = 0
    for i in range(1, N):
        ret += N / (N - i)
    print(ret)


if __name__ == '__main__':
    main()

考え方

ユーザ解説の「有効なのが来るまでカードを引く期待値は、有効なカードを引く確率の逆数になる」ということを知るまで全く理解できなかった。
例えば必ず均等に出目が決まる6面さいころを振って、１を出す確率は1 / 6で、
１が出るまでさいころを振る期待値は6 / 1の6回と言われると何となく理解できる。

次に、この問題では状態遷移についても考える必要がある。
頂点１以外未到達、 頂点の数をN個とすると未到達の頂点数はN - 1個となる。
移動可能な頂点数はN個のため、未到達の頂点に移動できる確率は(N - 1) / Nとなる。
逆数が期待値となるので、期待値はN / (N - 1)となる。

頂点１以外の異なる頂点に移動できたら、
次はN - 2個のまだ未到達の頂点に行くための期待値を求める。
こちらも1つ目と同様に期待値はN / (N - 2)となる。

あとは上記の通り、状態が変わる期待値を最後の１つになるまで求めて合算すると回答となる。