Pythonで「数を減らすゲーム」の勝者を求めるプログラム

問題の概要

AmalとBimalが一つのゲームをプレイしているとします。2人はある整数nを持っており、まずそれが2の累乗であるかどうかを確認します。もし2の累乗であれば、その数を2で割ります。そうでなければ、nより小さい最も近い2の累乗の数だけ値を減らします。そして、数を1にまで減らした方が勝者となります。Amalが必ず先手であるとき、勝者の名前を求めるプログラムを作成しましょう。

例として、入力が n = 19 の場合を考えてみます。19は2の累乗ではないため、Amalは16まで減らします。次にBimalが8にし、Amalが4に、Bimalが2にし、最後にAmalが1にして勝利します。したがって出力は「Amal」となります。

解法のアプローチ

この問題を解くには、以下の手順に従います。

• カウンタ res を0で初期化します。
• n が1より大きい間、以下を繰り返します。
  • b を1で初期化します。
  • b × 2 が n 未満である限り、b を2倍していきます(これにより n 未満の最大の2の累乗が得られます)。
  • n から b を引きます。
  • res を1増やします。
• ループ終了後、res が偶数であれば「Amal」を返します。
• 奇数であれば「Bimal」を返します。

このアルゴリズムでは、各操作(割り算または減算)を1回のターンとしてカウントしています。操作回数の偶奇によって、どちらのプレイヤーが最後の「1」への到達を行うかが決まるという仕組みです。

実装例

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

def solve(n):
   res = 0
   while(n > 1):
      b = 1
      while(b * 2 < n):
         b *= 2
      n -= b
      res += 1
   if res % 2 == 0:
      return 'Amal'
   else:
      return 'Bimal'

n = 19
print(solve(n))

入力

19

出力

Amal

計算量について

外側のwhileループは各反復で少なくとも半分以上の値を減らすため、全体の時間計算量は O(log² n) 程度となり、非常に効率的です。より高度な最適化としては、ビット演算を用いて n 未満の最大の2の累乗を求める方法や、n のビット長から直接操作回数を導出する方法もあります。