Pythonで解くミニオンゲーム：勝者の名前とスコアを求める方法

この記事では、「ミニオンゲーム」と呼ばれる文字列ゲームについて、勝者の名前とスコアを求めるPythonプログラムをわかりやすく解説します。

ゲームのルール

アマル（Amal）とビマル（Bimal）という2人のプレイヤーが、同じ文字列 s を使って対戦します。ルールは以下の通りです。

• 両プレイヤーとも同じ文字列 s を持ちます。
• それぞれ、s の文字を使って部分文字列（サブストリング）を作ります。
• ビマルは子音で始まる部分文字列だけを作ります。
• アマルは母音で始まる部分文字列だけを作ります。
• 両者が作成可能なすべての部分文字列を作り終えた時点でゲーム終了です。

スコアの計算方法

採点基準はシンプルです。作った部分文字列が元の文字列 s の中に出現するたびに1点が入ります。すべての部分文字列の出現回数を合計し、より高いスコアを獲得したプレイヤーが勝者となります。

例：「BANANA」の場合

入力が s = "BANANA" のとき、出力は「Bimal, 12」になります。内訳を表に整理すると次のようになります。

母音始まりの部分文字列の合計が9点、子音始まりの合計が12点となり、ビマルの勝利です。

効率的な解法のポイント

すべての部分文字列を実際に生成して数えると、時間計算量はO(n²)以上になり非効率です。ここで重要な気づきがあります。

インデックス i の文字から始まる部分文字列は、ちょうど「文字列の長さ − i」個存在します。

たとえば長さ6の "BANANA" では、先頭の 'B'（i=0）から始まる部分文字列は "B"、"BA"、"BAN"、"BANA"、"BANAN"、"BANANA" の6個です。つまり、各文字が母音か子音かを判定し、「n − i」を対応するプレイヤーのスコアに加算していくだけで、文字列を一度走査するだけで（O(n)で）合計スコアを求められます。

アルゴリズムの手順

• 母音の集合 vowels を用意します。
• スコア変数 p1（子音側＝ビマル）、p2（母音側＝アマル）を0で初期化します。
• 文字列中の各インデックス i と文字 c について次を繰り返します。
  • c が母音なら、p2 に「文字列の長さ − i」を加算する
  • それ以外なら、p1 に「文字列の長さ − i」を加算する
• p1 > p2 なら「Bimal」と p1 を返します。
• p2 > p1 なら「Amal」と p2 を返します。
• 同点の場合は「Draw」を返します。

Python実装例

以下のコードで、実際の動作を確認してみましょう。

def solve(word):
    vowels = set('AEIOU')
    p1 = 0
    p2 = 0
    for i, c in enumerate(word):
        if c in vowels:
            p2 += len(word) - i
        else:
            p1 += len(word) - i
    if p1 > p2:
        return 'Bimal', p1
    elif p2 > p1:
        return 'Amal', p2
    else:
        return 'Draw'

word = "BANANA"
print(solve(word))

入力

"BANANA"

出力

('Bimal', 12)

まとめ

この問題は一見、すべての部分文字列を列挙する必要がありそうですが、「位置 i の文字から始まる部分文字列は n − i 個ある」という性質を利用することで、線形時間 O(n) で勝者とスコアを求められます。文字列処理の定番テクニックのひとつなので、競技プログラミングやコーディング面接でも役立つ考え方です。ぜひ自分でも別の文字列で試してみてください。