Pythonで塔の高さを減らすゲームの勝者を求めるプログラム

問題の概要

高さがそれぞれ異なる n 本の塔があり、その高さが配列 height で与えられているとします。Amal(アマル)と Bimal(ビマル)の2人が、次のルールに従ってゲームを行います。

• Amal が必ず先手です。
• 各ターンで、手番のプレイヤーは高さ X の塔を1本選び、その高さを Y に変更します。ただし 1 <= Y < X であり、Y は X を割り切る必要があります。
• 最初に手を打てなくなったプレイヤーが負けとなります。

このゲームの勝者の名前を求めるのが目的です。

たとえば入力が height = [3,1,2] の場合、出力は Bimal になります。初期状態の高さは {3, 1, 2} です。Amal が高さ2の塔を1に減らすと、Bimal は高さ3の塔を1に減らすことができ、その後 Amal には有効な手が残らないため、Bimal の勝利となります。

解法のアプローチ

この問題は、ゲーム理論の基礎であるスプラーグ=グランディ定理(Nim の考え方)を応用して解くことができます。重要なポイントは、「高さ X の塔について、ゲーム終了までに打てる手の総数は、X を素因数分解したときの素因数の個数(指数も含む)に等しい」という性質です。

したがって、各塔について素因数の個数を求め、それらすべてを XOR した結果が 0 でなければ先手(Amal)の勝ち、0 なら後手(Bimal)の勝ちと判定できます。

アルゴリズムの手順

まず、補助関数 util() を定義します。この関数は配列 a とそのサイズ n を受け取り、全要素の XOR 値を返します。

• ans := 0 で初期化する
• i を 0 から n-1 までループし、ans := ans XOR a[i] を計算する
• ans を返す

メインの solve 関数では、次の処理を行います。

• n := 配列 height のサイズとする
• 長さ n の配列 b を用意し、すべて 0 で初期化する
• i を 0 から n-1 までループする:
  • height[i] が 1 の場合:b[i] := 0
  • それ以外の場合:b[i] := 0 とし、j := 2、root := height[i] の平方根の整数部分とする。height[i] が 1 でなく j <= root の間、次を繰り返す:
    • height[i] が j で割り切れる場合、割り切れなくなるまで b[i] を1ずつ増やしながら height[i] を j で割り続ける
    • j := j + 1
  • ループ後も height[i] が 1 でない場合(残った大きな素因数)、b[i] := b[i] + 1
• ans := util(b, n) を計算する
• ans が 0 以外なら "Amal"、0 なら "Bimal" を返す

実装例

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

def util(a,n):
    ans = 0
    for i in range(n):
        ans = ans^a[i]

    return ans

def solve(height):
    n = len(height)
    b = [0 for i in range(n)]

    for i in range(n):
        if(height[i] == 1):
            b[i] = 0
        else:
            b[i] = 0
            j = 2

            root = int(pow(height[i],0.5))
            while(height[i] != 1 and j<=root):
                if(height[i]%j == 0):
                    while(height[i]%j == 0):
                        b[i] += 1
                        height[i] = height[i]//j

                j += 1

            if(height[i] != 1):
                b[i] += 1

    ans = util(b, n)

    if(ans != 0):
        return "Amal"
    else:
        return "Bimal"

height = [3,1,2]
print(solve(height))

入力

[3,1,2]

出力

Bimal

まとめ

このプログラムは、各塔の高さを素因数分解することで「残りの手数」に相当するグランディ数を求め、それらの XOR 値によって勝者を判定します。試合の帰結は各塔の独立なサブゲームの組み合わせだけで決まるため、実際に手をシミュレートする必要はありません。各塔の計算量は O(√H) 程度に抑えられるため、非常に大きな高さの塔が含まれていても効率的に動作します。