Pythonで先手必勝を判定！目標スコア到達ゲームの勝敗チェックプログラム

問題の概要

2つの整数 k と target が与えられ、Amal（アマル）と Bimal（ビマル）の2人が交互にゲームを行う状況を考えます。各ラウンドでプレイヤーは 1 から k までの数字を1つ選び、0から始まる合計スコアに加算していきます。合計が target に到達させたプレイヤーの勝ちです。Amalが常に先手であり、両者が最適な戦略を取る場合、Amalが強制的に勝利できるかどうかを判定します。

例えば、k = 5、target = 10 の場合、出力は True になります。Amalが最初に4を選ぶと、Bimalが1〜5のどれを選んでも、次にAmalが5を選べば必ず10に到達できるためです。

解法のアプローチ

この問題は、シンプルな数学的性質を利用することで定数時間で解けます。手順は以下の通りです。

• target % (k + 1) の結果が 0 でない場合 → True（先手の勝ち）を返す
• 余りが 0 の場合 → False（先手は勝てない）を返す

なぜこの判定で正しいのか？

k + 1 は「1ターンで選べる数字の範囲＋1」に相当します。target が (k + 1) の倍数である場合、後手は常に「(k + 1) − 相手が選んだ数」を選ぶことで、各ラウンド終了時の合計を (k + 1) の倍数に保てます。そのため、最終的に target に到達するのは後手になります。

逆に target が (k + 1) の倍数でなければ、先手は最初に target % (k + 1) を選んで合計を調整し、以降は後手と同じ戦略を取ることで確実に勝利できます。

実装例

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

def solve(k, target):
    return target % (k + 1) != 0

k = 5
target = 10
print(solve(k, target))

入力

5, 10

出力

True