概要

\(N\) 枚のカードを連続する整数の集合（連番グループ）に分けるとき、グループ数を最小化する問題です。カードをソートして、連続していない箇所を数えることで解けます。

考察

重要な気づき

まず、連番グループとは何かを確認しましょう。例えば： - \(\{3, 4, 5\}\) は連番グループ（差がすべて \(1\)） - \(\{2, 4, 5\}\) は連番グループではない（\(2\) と \(4\) の差が \(2\)）

ポイント1: 各カードの値はすべて異なる（\(A_i \neq A_j\)）ので、同じ値のカードを考慮する必要がありません。

ポイント2: グループ数を最小にするには、できるだけ多くのカードを1つのグループにまとめたいです。つまり、連続している数はすべて同じグループに入れるべきです。

具体例で考える

入力が \(\{3, 1, 5, 2, 8, 7\}\) の場合を考えます。

ソートすると \(\{1, 2, 3, 5, 7, 8\}\) になります。

隣り合う要素の差を見ると： - \(2 - 1 = 1\) → 連続 ✓ - \(3 - 2 = 1\) → 連続 ✓ - \(5 - 3 = 2\) → 連続でない ✗（ここでグループが分かれる） - \(7 - 5 = 2\) → 連続でない ✗（ここでグループが分かれる） - \(8 - 7 = 1\) → 連続 ✓

結果として、\(\{1, 2, 3\}\)、\(\{5\}\)、\(\{7, 8\}\) の 3グループ に分かれます。

なぜソートするのか

連番グループは「昇順に並べたときに隣り合う差がすべて \(1\)」と定義されています。したがって、まずソートしてから連続性を確認するのが自然なアプローチです。

アルゴリズム

1. 配列 \(A\) を昇順にソートする
2. グループ数を \(1\) で初期化する（少なくとも1グループは必要）
3. 隣り合う要素を順番に比較し、差が \(1\) でなければグループ数を \(1\) 増やす
4. 最終的なグループ数を出力する

直感的な理解: ソート後の配列を左から見ていき、「連続が途切れた回数 \(+ 1\)」がグループ数になります。

ソート後: [1, 2, 3, 5, 7, 8]
          ├──連続──┤  │  ├連続┤
          グループ1  G2  グループ3

計算量

• 時間計算量: \(O(N \log N)\)

  • ソートに \(O(N \log N)\)
  • 配列を1回走査するのに \(O(N)\)
  • 全体では \(O(N \log N)\) が支配的

• 空間計算量: \(O(N)\)

  • 入力配列の格納に \(O(N)\)
  • ソートに使用する追加空間（Pythonの sort は \(O(N)\)）

実装のポイント

1. 初期値を1にする: 配列が空でない限り、最低でも1グループは存在します。ループでは「グループが分かれる箇所」を数えるので、初期値を1にしておきます。

2. ループの範囲: range(1, N) として、インデックス \(i\) と \(i-1\) を比較します。\(i = 0\) から始めると \(A[-1]\) を参照してしまうので注意。

3. \(N = 1\) の場合: ループが実行されず、そのまま \(1\) が出力されます。これは正しい動作です（カード1枚は1グループ）。

   ソースコード

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    # ソートする
    A.sort()
    
    # 連番グループの数をカウント
    # 隣り合う要素の差が1でない箇所でグループが分かれる
    groups = 1
    for i in range(1, N):
        if A[i] - A[i-1] != 1:
            groups += 1
    
    print(groups)

solve()

---

この解説は claude4.5opus によって生成されました。