Pythonでソート済みリストの重複を削除するゲームに必要なターン数を求めるプログラム

問題の概要

友人であるアマル（Amal）とビマル（Bimal）が、numsという名前のソート済み数値リストを使ってゲームを行っているとします。各ターンでは、まずアマルが任意の3つの数値を選び、次にビマルがそのうちの1つを削除し、続いてアマルがさらに1つを削除します。リストは最初、奇数個の要素で構成されています。

ここで、アマルはリストから重複要素をなくすために必要なターン数を最小化したいと考え、一方ビマルはターン数を最大化しようとします。両者が最適な戦略で行動するとき、このゲームが完了するまでに必要なターン数を求めるのが課題です。

入出力例

例えば、入力が nums = [1, 1, 2, 3, 3, 3, 4] の場合、出力は 2 になります。具体的な進行は以下の通りです。

• 1ターン目：アマルが [1, 1, 3] を選択 → ビマルはターンを延ばすために 3 を削除 → 配列は [1, 1, 2, 3, 3, 4] に → アマルが 1 を削除 → 配列は [1, 2, 3, 3, 4] になる
• 2ターン目：アマルが [3, 3, 4] を選択 → ビマルはターンを延ばすために 4 を削除 → アマルが 3 を削除 → 配列は [1, 2, 3] となり、重複要素がなくなる

解法のアプローチ

この問題は、隣接する重複ペアの数を数えることで効率的に解けます。手順は以下の通りです。

1. カウンター repeats を 0 で初期化します。
2. i を 1 から nums のサイズまで順に走査します。
3. nums[i] が nums[i-1] と等しい場合、repeats を 1 増やします。
4. 最後に (repeats + 1) // 2 を返します。

直感的には、各ターンで最大1組の隣接重複を解消できるため、必要なターン数は重複ペアの数を2で割って切り上げた値、すなわち (repeats + 1) // 2 に一致します。

実装例

class Solution:
   def solve(self, nums):
      repeats = 0
      for i in range(1, len(nums)):
         if nums[i] == nums[i-1]:
            repeats += 1
      return (repeats + 1) // 2
ob = Solution()
nums = [1, 1, 2, 3, 3, 3, 4]
print(ob.solve(nums))

入力

[1, 1, 2, 3, 3, 3, 4]

出力

2