Pythonでリストを長さk以上の厳密に増加するサブリストに分割できるか判定する方法

問題の概要

数値のリスト nums と別の値 k が与えられたとき、リストを「各サブリストの長さが k 以上」かつ「厳密に増加している(昇順)」という条件を満たすサブリスト群に分割できるかどうかを判定します。なお、分割後のサブリストは元のリスト内で連続した範囲である必要はありません。

例えば、nums = [6, 7, 5, 10, 13]、k = 2 の場合、出力は True になります。これは、リストを [5, 6] と [7, 10, 13] の2つのサブリストに分割でき、どちらも長さが2以上かつ厳密に増加しているためです。

解法のアプローチ

この問題は、各値の出現回数に着目することで効率的に解けます。手順は以下のとおりです。

• c: nums の各要素とその出現回数を格納したマップ(Counter)を作成する
• max_count: c における最大の出現頻度を求める
• max_count * k <= len(nums) であれば True を返し、そうでなければ False を返す

この判定が成り立つ理由は次のとおりです。ある値が max_count 回現れる場合、厳密に増加するサブリストの中に同じ値は1つしか含められないため、その値をすべて配置するには少なくとも max_count 個のサブリストが必要になります。さらに各サブリストの長さが k 以上でなければならないため、必要な要素数の下限は max_count * k となります。実際の要素数がこれを満たしていれば、必ず条件を満たす分割が存在します。

Pythonでの実装例

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

from collections import Counter

class Solution:
    def solve(self, nums, k):
        c = Counter(nums)
        max_count = max(v for num, v in c.items())
        return max_count * k <= len(nums)

ob = Solution()
nums = [6, 7, 5, 10, 13]
k = 2
print(ob.solve(nums, k))

入力

[6, 7, 5, 10, 13], 2

出力

True

この例では、すべての要素が1回しか現れないため max_count = 1 となり、1 * 2 = 2 <= 5 が成立するため True が返されます。計算量は Counter の構築と最大値の探索のみで済むため、O(n) と非常に効率的です。