Pythonでリストを長さ3以上の連続増加部分列に分割できるか判定するプログラム

問題の概要

非減少順（昇順）にソートされた数値リスト nums が与えられます。このリストを任意の個数の部分列に分割できるかどうかを判定してください。ただし、各部分列は最小長3以上であり、かつ連続的に増加している必要があります。

たとえば、入力が nums = [2, 3, 4, 4, 5, 6, 7] の場合、出力は True になります。これは、リストを [2, 3, 4] と [4, 5, 6, 7] という2つの部分列に分割でき、どちらも条件を満たすためです。

解法の考え方

この問題のポイントは、各値 x について「x から始まる部分列の数」と「x で終わる部分列の数」を求めることです。値 x の出現回数を count[x] とすると、次の関係が成り立ちます。

• x から始まる部分列の数 ＝ count[x] - count[x-1]
• x で終わる部分列の数 ＝ count[x] - count[x+1]

すべての部分列が長さ3以上であるためには、開始値 s と終了値 e のすべてのペアが s + 2 <= e を満たす必要があります。この条件を全ペアでチェックすれば答えが得られます。

アルゴリズムの手順

• counts：nums の各要素とその出現回数を格納したマップを作成する
• starts：部分列の開始値を記録する空のリストを用意する
• ends：部分列の終了値を記録する空のリストを用意する
• キーをソートした順に各要素 x について以下を処理する
  • count[x] > count[x - 1] の場合、x を (count[x] - count[x - 1]) 個だけ starts に追加する
  • count[x] > count[x + 1] の場合、x を (count[x] - count[x + 1]) 個だけ ends に追加する
• すべての (start, end) ペアが start + 2 <= end を満たせば true を返し、そうでなければ false を返す

Pythonでの実装例

理解を深めるために、以下の実装例を見てみましょう。

from collections import Counter

class Solution:
    def solve(self, nums):
        count = Counter(nums)
        starts = []
        ends = []
        for x in sorted(count):
            if count[x] > count[x - 1]:
                starts.extend([x] * (count[x] - count[x - 1]))
            if count[x] > count[x + 1]:
                ends.extend([x] * (count[x] - count[x + 1]))
        return all(s + 2 <= e for s, e in zip(starts, ends))

ob = Solution()
nums = [2, 3, 4, 4, 5, 6, 7]
print(ob.solve(nums))

実行結果

上記のコードを実行すると、次の出力が得られます。

True

リスト [2, 3, 4, 4, 5, 6, 7] は [2, 3, 4] と [4, 5, 6, 7] に分割できるため、正しく True が出力されています。

計算量

このアルゴリズムの時間計算量は O(n log n)（主にキーのソートコスト）、空間計算量は O(n) です。開始値と終了値の対応関係が明確でロジックが理解しやすいのが特徴です。