概要

与えられた整数の列を、連続する数字からなるグループ（連番グループ）に分割するとき、必要なグループ数の最小値を求めます。

考察

この問題では、カードに書かれた数字をいくつかの「連続した整数の列」に分割するのが目的です。
例えば、カードの数字が \(\{3, 5, 4, 7, 6\}\) であれば、これらはすべて連続しているので1つのグループにできます。
一方で \(\{1, 3, 5\}\) のように飛び飛びの場合は、それぞれ別のグループにする必要があります。

素朴な方法として、貪欲に連続する数字をつなげていくことを考えます。
しかし、単純に配列の順番で見ると、元の入力がソートされていない場合、連続性を見逃す可能性があります。
そこで、まずカードの数字をソートして、小さい順に処理することを考えます。

さらに、同じ数字が複数枚ある場合（制約上は今回はありませんが）、あるいはアルゴリズム的に効率よく管理するために、各数字の出現回数を管理する辞書を使うのが有効です。

この問題の肝は、「連続する数字を最大限につなげて1つのグループとする」ことで、グループ数を最小にできるという点です。
具体的には、ある数字 \(x\) がまだ使われていなければ、そこから始まる連続列 \(x, x+1, x+2, \ldots\) を作れるだけ作り、それが1つのグループになります。これを繰り返すことで全体を最適に分割できます。

アルゴリズム

1. カードに書かれた整数列 \(A\) をソートする。
2. 各数字の出現回数を記録する（今回は重複がないので1回ずつ）。
3. 小さい方から数字を見て、その数字から始まる連続列を作れるだけ作る：
   • 今見ている数字 \(num\) がまだ残っていれば、そこから連続する数字 \(num+1, num+2, \ldots\) を順に使っていき、途切れたら終了。
   • この一連の操作で1つの連番グループが完成する。
4. 上記をすべての数字に対して行い、作られたグループ数をカウントする。

例

入力例：

5
3 5 4 7 6

• ソートすると：\(\{3, 4, 5, 6, 7\}\)
• 最初の3から連続して7まで使える → 1グループ
• 結果：グループ数は \(1\)

もう一つの例：

4
1 3 5 7

• どれも連続していない → 各数字が別々のグループ
• 結果：グループ数は \(4\)

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（出現回数を記録する辞書）

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用。
• 各数字の出現回数を defaultdict で管理することで、存在しないキーへのアクセスでもエラーが出ない。
• 数字をソート済みの順に処理することで、連続性を確実に判定できる。
• 各数字を使い切るまでループし、連続する数字をどんどん消費していくことで、貪欲に最適なグループを作っている。

## ソースコード

```python
import sys
from collections import defaultdict

def main():
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    A = list(map(int, data[1:N+1]))
    
    # Sort the array to process in order
    A.sort()
    
    # Dictionary to count how many times each number appears
    count = defaultdict(int)
    for num in A:
        count[num] += 1
    
    groups = 0
    
    # Process each unique number in sorted order
    for num in sorted(count.keys()):
        # While there are still cards with this number
        while count[num] > 0:
            # Start a new group
            current = num
            count[current] -= 1
            # Extend the group as far as possible
            while count[current + 1] > 0:
                current += 1
                count[current] -= 1
            groups += 1
    
    print(groups)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。