Pythonで与えられたリストが有効な状態かどうかをチェックするプログラム

問題の概要

nums という数値のリストが与えられたとき、リスト内のすべての数字を次のいずれかのルールでグループ化できるかどうかを判定します。

• 連続する2つの同じ数字からなるペア (a, a)
• 連続する3つの同じ数字からなるトリプレット (a, a, a)
• 連続する3つの連番からなるトリプレット (a, a+1, a+2)

たとえば、入力が nums = [7, 7, 3, 4, 5] の場合、[7, 7] をペアとして、[3, 4, 5] を連番のトリプレットとしてそれぞれグループ化できるため、出力は True になります。

解決のアプローチ：動的計画法（DP）

この問題は、動的計画法を使うことで効率的に解くことができます。dp[i] を「リストの先頭から i 番目までの要素がすべてルールに従ってグループ化できるか」を表す真偽値と定義し、先頭から順に状態を更新していきます。

具体的な手順は以下の通りです。

• n := nums のサイズとする
• dp := サイズ n+1 のリストを作成し、最初の要素を True、残りを False で初期化する
• i を 2 から n まで繰り返す
  • i ≥ 2 かつ dp[i−2] が True の場合、nums[i−1] と nums[i−2] が等しければ dp[i] := True とする（ペアでのグループ化）
  • i ≥ 3 かつ dp[i−3] が True の場合、「nums[i−1]、nums[i−2]、nums[i−3] がすべて等しい」または「nums[i−1] == nums[i−2]+1 == nums[i−3]+2」が成り立てば dp[i] := True とする（トリプレットでのグループ化）
• 最後に dp[n] を返す

実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution:
   def solve(self, nums):
      n = len(nums)
      dp = [True] + [False] * n
      for i in range(2, n + 1):
         if i >= 2 and dp[i - 2]:
            if nums[i - 1] == nums[i - 2]:
               dp[i] = True
         if i >= 3 and dp[i - 3]:
            if (nums[i - 1] == nums[i - 2] == nums[i - 3]) or (nums[i - 1] == nums[i - 2] + 1 == nums[i - 3] + 2):
               dp[i] = True
      return dp[n]
ob = Solution()
nums = [8, 8, 4, 5, 6]
print(ob.solve(nums))

入力

[8, 8, 4, 5, 6]

出力

True

コードのポイント

このアルゴリズムの計算量は O(n)、必要なメモリも O(n) であり、非常に効率的です。dp テーブルによって「どこまでの範囲が正しくグループ化できているか」という状態を管理しながら、ペアまたはトリプレットのどちらかで区切れる位置ごとに True を伝播させていくのがポイントです。これにより、ネストしたループや再帰を使わずに、シンプルな線形走査で答えを求められます。