概要

\(N\) 枚の異なる整数が書かれたカードを、昇順に並べたときに値が \(1\) ずつ増加する「連番グループ」に分けるとき、最小で何個のグループが必要かを求める問題です。

考察

この問題を解くための重要なポイントは、「カードをどのような順番で並べても、最終的なグループ分けには影響しない」という点です。したがって、まずはカードを昇順にソートして考えるのが自然です。

例えば、カードが \(\{3, 5, 4, 8, 7\}\) のとき、これらをソートすると \(\{3, 4, 5, 7, 8\}\) となります。 - \(3\) と \(4\) は連続している（差が \(1\)）ので、同じグループに入れられます。 - \(4\) と \(5\) も連続している（差が \(1\)）ので、同じグループに入れられます。 - \(5\) と \(7\) は連続していない（差が \(2\)）ため、どうしてもここでグループを分けなければなりません。 - \(7\) と \(8\) は連続している（差が \(1\)）ので、同じグループに入れられます。

結果として、\(\{3, 4, 5\}\) と \(\{7, 8\}\) の \(2\) つのグループに分けるのが最適（最小）であることがわかります。

つまり、ソート済みの配列において「隣り合う要素の差が \(1\) ではない箇所」がいくつあるかを数えることで、必要なグループの数を特定できます。新しいグループが必要になるのは、常に「前のカードと値が連続していないカード」が現れたタイミングです。

アルゴリズム

1. 与えられた \(N\) 枚のカードの数値 \(A_i\) を配列に格納し、昇順にソートします。
2. グループ数のカウント（ans）を \(1\) に初期化します（カードが \(1\) 枚以上あれば、最低でも \(1\) つのグループは存在するため）。
3. 配列を先頭から走査し、隣り合う要素 \(A_i\) と \(A_{i+1}\) を比較します。
4. もし \(A_{i+1} \neq A_i + 1\) であれば、値が連続していないため、ans を \(1\) 加算します。
5. 最終的な ans の値を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • カードのソートに \(O(N \log N)\) かかります。
  • その後の配列の走査は \(O(N)\) です。
  • 全体としてソートの計算量が支配的になりますが、\(N = 2 \times 10^5\) であれば制限時間内に十分間に合います。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 枚のカードを保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Pythonの場合、sys.stdin.read().split() を使うことで、大量の入力を一括で読み込むことができ、実行時間の短縮につながります。

• 隣り合う要素の比較: ループの範囲を \(N-1\) までに設定し、A[i] と A[i+1] を比較することで、配列の範囲外参照を防ぎながら正しく判定できます。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを取得し、空白（スペースや改行）で分割してリストにする
    # この方法は大量の入力を高速に読み込むのに適しています
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は何もせず終了
    if not input_data:
        return
    
    # 最初の値がカードの枚数 N
    n = int(input_data[0])
    
    # 残りの値が各カードに書かれた整数 A_i
    # 整数型のリストに変換する
    a = list(map(int, input_data[1:]))
    
    # カードに書かれた整数を昇順にソートする
    # 連番グループを特定しやすくするため
    a.sort()
    
    # カードが0枚の場合はグループ数も0（制約上は 1 <= N）
    if n == 0:
        print(0)
        return
    
    # 最小のグループ数を求める
    # ソートされた状態で、隣り合う要素の差が1でない箇所があるたびに
    # 新しいグループが必要になる
    ans = 1
    for i in range(n - 1):
        # 隣り合う整数の差が1でない場合、そこは連番ではない
        if a[i+1] != a[i] + 1:
            ans += 1
    
    # 結果を出力する
    print(ans)

if __name__ == '__main__':
    main()

この解説は gemini-3-flash-thinking によって生成されました。