Pythonで配列内の要素のペアワイズ差を追加し続け、ゲームの勝者を見つける方法

問題概要

正の整数のみで構成され、要素がすべて重複のない配列Aがあるとします。ここで、2人のプレイヤーPとQがこの配列を使ってゲームを行います。各手番では、どちらか一方のプレイヤーが配列から2つの数値aとbを選び、絶対差 |a – b| がまだ配列に存在しなければ、その値を新たに配列へ追加します。新しい数を追加できなくなったプレイヤーが負けとなります。プレイヤーPが常に先攻であるとき、このゲームの勝者が誰になるかを求めるのが課題です。

たとえば、入力が A = [8,9,10] の場合、出力は「P」になります。

解法のアプローチ

この問題の鍵を握るのは最大公約数（GCD）です。配列内の任意の2つの数の差もまた、それらのGCDの倍数になります。そのため、ゲームが続く限り、配列には最終的に「全体のGCD（g）の倍数」だけが残ることになります。

ゲーム終了時点では、g から max_val（配列の最大値）までの g の倍数がすべて揃っている状態になります。つまり、ゲーム全体で行われた追加の手数は次のように表せます。

total = (max_val ÷ g) − n

Pが先攻なので、total が奇数であれば最後の手を打つのは P となり、P が勝者です。偶数であれば Q が勝者となります。具体的な手順は以下の通りです。

• n := 配列arrのサイズとする
• g := arr[0]、max_val := arr[0] で初期化する
• i を 1 から n−1 まで繰り返す
  • g := gcd(g, arr[i])
  • max_val := max_val と arr[i] のうち大きい方
• total := (max_val / g) − n を計算する
• total が奇数であれば「P」を返す
• そうでなければ「Q」を返す

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

from math import gcd

def who_is_the_winner(arr):
    n = len(arr)
    g = arr[0]
    max_val = arr[0]
    for i in range(1, n):
        g = gcd(g, arr[i])
        max_val = max(max_val, arr[i])
    total = (max_val // g) - n  # 整数除算を使用
    if total % 2 == 1:
        return 'P'
    return 'Q'

arr = [8, 9, 10]
print(who_is_the_winner(arr))

入力

[8,9,10]

出力

P

まとめ

このアルゴリズムは、配列を一度走査するだけで済むため、時間計算量は O(n)、空間計算量も O(1) と非常に効率的です。ゲームを実際にシミュレーションすることなく、GCDと偶奇の性質だけで勝者を即座に判定できる点がポイントです。