Pythonで最後に風船を受け取る子供の開始インデックスを求める方法

n人の子供が円形に並んでいて、順番に風船を受け取る場面を考えてみましょう。配布はk番目の子供（最初のインデックスは0）から始まり、風船をもらった子供はその場で円から外れます。その後も時計回りにk番目ごとの子供へ風船が渡され、最後に残った1人の子供が風船を受け取ります。ここで、nとkが与えられたとき、最後に風船を受け取る子供の開始インデックスを求めるのがこの問題です。

具体例で理解する

例えば、入力が n = 3、k = 2 の場合を考えてみます。

• 1回目： 子供2が風船を受け取り、円から外れます。残りは [0, 1] になります。
• 2回目： 子供0が風船を受け取り、円から外れます。残りは [1] だけになります。

したがって、出力は 1 となります。

解法のアプローチ

この問題は、いわゆる「ジョセファスの問題」と同じ構造を持っています。リストを実際に操作してシミュレーションすることで解けます。手順は以下の通りです。

1. arr := 0からn-1までの値を持つ新しいリストを作成する
2. init := 0 と初期化する
3. arrのサイズが1より大きい間、以下を繰り返す
   • remove := (init + k) mod arrのサイズ を計算する
   • arr[remove] を削除する
   • init := remove と更新する
4. arr[0] を返す

実装コード

それでは、上記の手順をPythonで実装してみましょう。

class Solution:
    def solve(self, n, k):
        arr = list(range(0, n))
        init = 0
        while len(arr) > 1:
            remove = (init + k) % len(arr)
            del arr[remove]
            init = remove
        return arr[0]

ob = Solution()
n = 3
k = 2
print(ob.solve(n, k))

入力

3, 2

出力

1

計算量について

このシミュレーション方式では、各ラウンドで要素を1つ削除するため、時間計算量はO(n²)、空間計算量はO(n)となります。nが小さい場合は十分実用的ですが、nが非常に大きい場合は再帰式を用いた数学的な解法（O(n)やO(log n)）を検討するとよいでしょう。