概要

与えられたカードを連続した整数からなるグループ（連番グループ）に分割するとき、グループ数の最小値を求める問題です。

考察

カードを連番グループに分割する際、重要な観察は「連続する整数は同じグループに含めることができる」という点です。例えば、カード [1,2,3,5,6] がある場合、[1,2,3] と [5,6] の2つのグループに分けることができます。

素朴なアプローチとして、すべての可能な分割を試す方法が考えられますが、カードの枚数 \(N\) が最大 \(2 \times 10^5\) と大きいため、指数時間アルゴリズムでは計算が間に合いません。

効率的な解法として、カードをソートした後、貪欲法でグループを作成する方法が有効です。ソート後のカードを先頭から順に見ていき、現在のグループに含められるカード（現在の値+1以下の値）を可能な限り追加していきます。これにより、各グループを可能な限り長く伸ばすことができ、結果としてグループ数を最小化できます。

アルゴリズム

1. カードに書かれた整数を昇順にソートする
2. 先頭から順にカードを見ていき、以下の手順でグループを作成する：
   • 現在のカードを新しいグループの開始点とする
   • 次のカードが現在の値+1以下である間、グループに追加する
     • ちょうど現在の値+1のカードを見つけたら、現在の値を+1更新する
   • グループに追加できなくなった時点でグループを確定し、次のカードから新しいグループを開始する
3. 作成したグループの総数を出力する

この貪欲法は、ソート済みの配列を一度走査するだけで最適なグループ分割を求めることができます。

計算量

• 時間計算量: \(O(N \log N)\)（ソートの計算量が支配的）
• 空間計算量: \(O(N)\)（入力データを格納するための配列）

実装のポイント

• 入力データを一度に読み込むことで効率化

• ソート後に貪欲にグループ化する際、二重ループを使用しているが、外側のループと内側のループで各要素は高々1回しか処理されないため、全体の計算量は \(O(N)\)

• 現在のグループの終端値を追跡しながら、次のカードがグループに含めるかどうかを判定する

• 内側のループ条件で A[j] <= current + 1 とすることで、重複する値がないため、連続性を保ちつつ効率的にグループ化できる

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    A = list(map(int, data[1:1+n]))
    
    A.sort()
    count = 0
    i = 0
    while i < n:
        count += 1
        current = A[i]
        j = i + 1
        while j < n and A[j] <= current + 1:
            if A[j] == current + 1:
                current += 1
            j += 1
        i = j
        
    print(count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。