「ゲームを排除する」ための効率的なアルゴリズムの構築

Question

私はこのエリミネーションゲームの問題を解決していました。

まず、力ずくで試してみました。

• 距離から始まる数を削除 $2$ （つまり、次の要素の後の要素）
• リストを逆にしました
• 距離とともに最初から数字を削除 $2$
• リストを逆にしました...

最後に、最後に残った要素を返しました。ただし、当然のことながら、これにより「制限時間超過」が発生しました。

このためのPythonコードは次のとおりです。

def lastRemaining(n: int) -> int:
        nums = [i for i in range(1, n + 1)]
        l = len(nums)
        while l != 1:
            for i in range(0, len(nums), 1):
                if i < len(nums): 
                    nums.remove(nums[i])
                    l -= 1
            nums.reverse()
        return nums[0]

次に、より良い解決策を探して、次のことを見つけました。

def lastRemaining(n: int) -> int:
        if n == 1: return 1
        return (n//2 - lastRemaining(n//2) + 1) * 2

そしてそれは動作します。これは数学的に次のように書かれています$$ f(n) = \begin{cases} 1, \text{ if } n=1, \\ 2\left(\bigg\lfloor\cfrac{n}{2}\bigg\rfloor - f\left(\bigg\lfloor\cfrac{n}{2}\bigg\rfloor\right) + 1\right), \text{ otherwise } \end{cases} $$ 私はこれをいくつかの値について検証しました $n$。それでも、このアルゴリズムがすべての場合に機能することを証明するための支援が必要です。

どんな助けでも大歓迎です。

Answer 1

最初のケース $n=1$明らかです。2番目のケースでは、基本的に最初の反復を実行し、残りの問題を解決していることに注意してください（$2, 4, 6, ... 2⌊n/2⌋$） - よくほとんど。あなたはそれを逆の順序で行います、それがあなたが持っている理由です$⌊n/2⌋-f(⌊n/2⌋)+1$ の代わりに $f(⌊n/2⌋)$ここでは、実際には「最後の番号」の順序を返しているのであって、その値ではないことに注意してください。これは、元の問題と同等です。したがって、$2$ 最後に、順序がわかっている「最後の数」の値を取得します。