CodeIQ「『マイナー・ゲーム』問題」の掲載期間が終わったということで、自分の提出コードを公開しておきます。なお詳しい問題の概要や解法は広大なWebの海にあると思うので、見つけ出してください~~(実はわたしも詳しい問題の中身を覚えていないというのは内緒)~~。またほかの方が公開されたコードがTogetterにまとまられておりますので、そちらのほうもぜひ。

# m個からn個を選ぶ組み合わせを返す
c_memo = {}
def C(m, n):
    if (m, n) in c_memo: return c_memo[(m, n)]

    c_memo[(m, n)] = 1 if m == n or n == 0 else C(m - 1, n - 1) + C(m - 1, n)
    return c_memo[(m, n)]

# 少数決によってx人からy人になる確率
# cf. x人からy人になる確率 = (2 * C(x, y)) / (2 ** x)
g_memo = {}
def G(x, y):
    if (x, y) in g_memo: return g_memo[(x, y)]

    if x == y:
        if x % 2 == 0: # ex. G(4, 4): 4人から4人になる確率 + 引き分ける確率
            g_memo[(x, y)] = (2 * C(x, y)) / (2 ** x) + (C(x, y // 2)) / (2 ** x)
        else:
            g_memo[(x, y)] = (2 * C(x, y)) / (2 ** x)
    else:
        if x - y <= y: # ex. G(4, 3): 4人から3人になることはない
            g_memo[(x, y)] = 0
        else:
            g_memo[(x, y)] = (2 * C(x, y)) / (2 ** x)

    return g_memo[(x, y)]

# 問題文中のF(n)
def F(n):
    exps = [-1, 0]
    game = 1

    pros = [0 for _ in range(n + 1)]
    pros[n] = 1

    while exps[-2] != exps[-1]: # 期待値の変化が見られなくなるまでループ
        new_pros = [0 for _ in range(n + 1)]
        for x in (*range(3, n // 2 + 1), n):
            for y in range(1, x + 1): new_pros[y] += pros[x] * G(x, y)

        exps.append(exps[-1] + game * (new_pros[1] + new_pros[2]))
        pros = new_pros
        game += 1

    return int(exps[-1] * (10 ** 6))


if __name__ == '__main__':
    n = int(input())
    print(F(n))

    """
    n = 7のとき、ゲームが進むにつれて、考えられる人数は次のように推移していく

    start  1回目   2回目  3回目
　　*****************************
     7人    1人     1人    1人
            2人     2人    2人
            3人     3人    3人
            7人     7人    7人
    """

たとえば7人で一連のゲームを始めるとします。まず1回目の少数決の結果、残る人数は1人・2人・3人・7人のどれかに決まります。1人と2人の場合、ルール上ゲームが終わってしまうので、2回目の少数決の対象になるのは3人もしくは7人の場合です。

3人で少数決を行うと、残る人数は1人もしくは3人です。7人の場合は言うまでもなく、1人・2人・3人・7人のどれかです。つまり7人で始めたゲームについて、2回の少数決を行ったとき、残る人数の組み合わせは1人・2人・3人・7人に決まります。

わたしの解法は以上のような手続き(?)を模したものといえます。___つまり少数決を1回1回進めながら、残った人数について確率を求め、それをもとに期待値を計算しているのです。___あるいは少数決の回数を重ねながら、期待値を正解に近づけていく解き方と言い換えることができるかもしれません。

この解法の問題は「終わりがない」ということ。少数決の回数はいくらでも増やすことができるので、どこかのタイミングでゲームを中断してやる必要があります。そこで今回は___期待値に変動がなくなった時点で、十分正解に近づいたと判断し、ゲームを中断することにしました。___

疲れた身体で書いているせいか、解法の説明がポエムみたいになっています(´・ω・`)
これを解いていた当時は再帰に凝っていたらしく、コード全体が(メモ化)再帰まみれ(´・ω・`)
社会人になって3か月も経ってないのに、もうつらい(´・ω・`)