Pythonで解く文字並べ替えゲーム：回文を作れるプレイヤーの勝者を判定するアルゴリズム

問題の概要

小文字の英字のみで構成される文字列 S があるとします。この文字列を使って、2人のプレイヤーが次のルールでゲームを行います。

• どの手番においても、文字列の文字を自由に並べ替えて回文（前から読んでも後ろから読んでも同じになる文字列）を作ることができれば、その手番のプレイヤーの勝ちとなります。
• 回文が作れず、文字を1つ削除しなければならない状況になったプレイヤーは、その時点では勝利できません。

両プレイヤーは常に最適な手を選ぶものとし、先手はプレイヤー1です。このとき、ゲームの勝者が誰になるかを求めるのが本記事のテーマです。

例えば、入力が「pqpppq」だった場合、答えは Player1 になります。プレイヤー1は最初の手番で文字を並べ替えて「ppqqpp」を作ればよいので、即座に勝利できるからです。

アルゴリズムの考え方

ここで重要になるのが回文の性質です。回文では、奇数回出現する文字は高々1種類しか存在できません（文字列の長さが奇数の場合の中央の1文字だけが例外です）。

そこで、各文字の出現回数を数え、「奇数回出現する文字の種類数」を count とすると、次のように勝敗を判定できます。

• count が 0 の場合：すべての文字が偶数回出現しているため、手番のプレイヤーはすぐに並べ替えて回文を作り、勝利できます。
• count が奇数の場合：手番のプレイヤーは文字を1つ削除することで count を偶数にできます。相手は必ず count を奇数に戻す操作を強いられ、最終的に回文を作れるタイミングを掴むのは先手側です。

以上のことから、count が 0 または奇数ならプレイヤー1の勝ち、偶数（かつ0以外）ならプレイヤー2の勝ちであることが分かります。

解法の手順

1. l := 文字列の長さとする
2. freq := サイズ26のリストを用意し、すべて0で初期化する（各アルファベットの出現回数を記録）
3. 文字列を先頭から走査し、各文字の出現回数を freq に加算する
4. count := 0 とし、freq の中で奇数になっている要素の個数を数える
5. count が 0 または奇数であれば 1（プレイヤー1の勝ち）を返す
6. それ以外の場合は 2（プレイヤー2の勝ち）を返す

実装例

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

def who_is_the_winner(sequence):
    l = len(sequence)
    freq = [0 for i in range(26)]
    for i in range(0, l, 1):
        freq[ord(sequence[i]) - ord('a')] += 1
    count = 0
    for i in range(26):
        if (freq[i] % 2 != 0):
            count += 1
    if (count == 0 or count & 1 == 1):
        return 1
    else:
        return 2

sequence = "pqpppq"
print("Player:", who_is_the_winner(sequence))

入力

"pqpppq"

出力

Player: 1

まとめ

この問題は、回文の「奇数回出現する文字は高々1種類」という性質を利用することで、文字列を1回走査するだけで O(n) の計算量で勝者を判定できます。ゲーム理論的な考察が必要に見えますが、結局は「奇数回出現する文字の種類数の偶奇」だけに着目すればよい、という点がポイントです。