概要

与えられた \(N\) 枚のカード（すべて異なる整数）を、各グループが「連続する整数列」になるように分けるとき、必要なグループ数の最小値を求めます。

考察

「連番グループ」は、含まれる数を昇順に並べたとき隣同士の差がすべて \(1\) になる集合です。
この条件を満たすには、同じグループ内の値は必ず連続した整数でなければなりません。

ここで重要な気づきは次の通りです：

• カードの数値を昇順に並べると、同じ連番グループに入れられるのは「隣り合う値の差が \(1\) の区間」だけ。
• 逆に、昇順に並べたとき 差が \(1\) でない場所（ギャップ） があると、そこは必ずグループの切れ目になります。なぜなら、間の整数が存在しない以上、同じグループにすると「差が \(1\)」条件を壊してしまうからです。

したがって、 - グループ数の最小値 =（昇順で見たときの「差が \(1\) でない箇所」の数）+ 1 になります。

素朴に「どのカードをどのグループに入れるか」を探索したり、グルーピングを試行錯誤すると組合せ爆発してしまい、\(N \le 2 \times 10^5\) では現実的に間に合いません。
しかし、上の観察により「並べて差を見るだけ」で答えが決まります。

例：\(A=\{3,5,4,10,11\}\)
昇順にすると \([3,4,5,10,11]\)
差は \(1,1,5,1\) なので、差が \(1\) でないのは \(5\) の1箇所 → グループ数は \(1+1=2\)（\(\{3,4,5\}\) と \(\{10,11\}\)）

アルゴリズム

1. 配列 \(A\) を昇順にソートする。
2. グループ数 groups を \(1\) で初期化する（\(N \ge 1\) なので最低1グループは必要）。
3. \(i=1\) から \(N-1\) まで順に見て、\(A[i]-A[i-1] \neq 1\) なら groups を \(1\) 増やす。
4. groups を出力する。

計算量

• 時間計算量: ソートにより \(O(N \log N)\)、差分チェックは \(O(N)\) なので合計 \(O(N \log N)\)
• 空間計算量: ソート済み配列などで \(O(N)\)

実装のポイント

• \(A_i\) は最大 \(10^9\) ですが、差分計算は Python の整数で安全に扱えます。

• \(N=1\) のときも正しく \(1\) を出力できるよう、初期値を groups = 1 にします。

• 入力が大きいので sys.stdin.readline を使うと安定します。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    A = list(map(int, input().split()))
    A.sort()
    groups = 1
    for i in range(1, N):
        if A[i] - A[i - 1] != 1:
            groups += 1
    print(groups)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。