Pythonでセット要素除去ゲームの勝者を判定するプログラムを作成する方法

問題概要

1からnまでの自然数の集合 {1, 2, ..., n} があります。Amal(アマル)と Bimal(ビマル)の2人が、この集合を使って以下のルールでゲームを行います。

• 必ず Amal が先手です。

• 各ターンで、手番のプレイヤーは集合の中から素数 p を1つ選び、p とその倍数をすべて集合から取り除きます。

• 手を打てなくなったプレイヤーの負けです。n が与えられたとき、勝者の名前を求めてください。

例えば入力が n = 5 の場合、出力は「Amal」になります。初期状態の集合は {1, 2, 3, 4, 5} です。まず Amal が p = 2 を選ぶと、2 と 4 が取り除かれて集合は {1, 3, 5} になります。ここで残っている素数は 3 と 5 の2つなので、Bimal がどちらを選んでも新たに取り除ける要素はなく、最後に Amal が残りの素数を取り除いて勝利します。

考え方(アルゴリズム)

このゲームの鍵は、「1回の手番につき必ず素数が1つ消費される」という点です。合成数は素数を選んだ際に一緒に取り除かれますが、合成数そのものを選ぶことはできません。また、1 はどの素数の倍数でもないため最後まで残りますが、素数ではないので選択対象になりません。

したがって、ゲーム全体の手番数は「n 以下の素数の個数」と一致します。この個数が奇数なら先手の Amal が最後の手を打てるため勝ち、偶数なら後手の Bimal が勝ちます。

そこで、エラトステネスの篩(ふるい)の要領で、2から順に各数に対して「それ以下の素数の個数」を累積的に記録した配列 primes を事前に構築しておけば、任意の n に対して O(1) で答えを返せます。

解法手順

• primes:サイズ 100000 の配列を用意し、すべて 0 で初期化します(n 以下の素数の累積個数を格納)。

• sieve:同じくサイズ 100000 の配列を用意し、すべて 0 で初期化します(最小の素因数を記録するフラグとして使用)。

• i を 2 から 99999 まで順に処理します。

  • sieve[i] が 0 の場合(i が素数):

    • primes[i] := primes[i-1] + 1

    • j を i から 100000 まで i 刻みで走査し、sieve[j] := i と更新します。

  • それ以外の場合(合成数):

    • primes[i] := primes[i-1](個数をそのまま引き継ぐ)

• メイン処理では、primes[n] が奇数なら「Amal」、偶数なら「Bimal」を返します。

実装例(Python)

理解を深めるために、以下の実装例を見てみましょう。

primes = [0 for i in range(100001)]
sieve = [0 for i in range(100001)]
for i in range(2, 100000):
    if sieve[i] == 0:
        primes[i] = primes[i-1]+1

        for j in range(i, 100001, i):
            sieve[j] = i
    else:
        primes[i] = primes[i-1]

def solve(n):
    return "Bimal" if primes[n] % 2 == 0 else "Amal"

n = 5
print(solve(n))

入力

5

出力

Amal

計算量

ふるいの構築には O(N log log N)(ここでは N = 100000)かかり、各クエリへの回答は O(1) です。前計算を一度行えば、複数の異なる n に対しても高速に勝者を判定できるのが大きなメリットです。