プログラマーのスキルセットから形成できるグループの最小数を求めるC++プログラム

問題の概要

n個の要素を持つ配列Aがあるとします。A[i]はi番目の学生のプログラミングスキルを表しており、配列内のすべての要素は互いに異なります。これらの学生を、次の条件を満たすようにチームへ分割することを考えます。

• |A[i] − A[j]| = 1 となるような2人の学生(iとj)が、同じチームに所属しないこと
• チームの数は可能な限り少なくすること

たとえば、入力が A = [2, 3, 4, 99, 100] の場合、出力は 2 となります。スキルが連続する値(2と3、99と100など)を持つ学生同士は同じチームに入れないため、最低でも2つのチームが必要になるからです。

解法の考え方(ステップ)

この問題は、次の手順で解くことができます。

• 答えの候補として、変数 dem を 1 で初期化します。
• 配列 A を昇順にソートします。
• i を 1 から配列のサイズ未満まで増やしながらループ処理を行います。
• A[i] − A[i−1] が 1 と等しい場合、dem を 2 に更新します。
• 最終的な dem の値を返します。

ここでのポイントは、すべての要素が互いに異なるため、ソート後の配列を偶数番目と奇数番目に交互に振り分ければ、差が1となるペアを必ず別々のチームに配置できるという点です。したがって、答えは「差が1となる隣接ペアが存在するかどうか」だけで決まり、その値は必ず 1 または 2 のどちらかになります。

実装例(C++)

より理解を深めるために、実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
    int dem = 1;
    sort(A.begin(), A.end());
    for (int i = 1; i < A.size(); i++)
        if (A[i] - A[i - 1] == 1)
            dem = 2;
    return dem;
}

int main() {
    vector<int> A = { 2, 3, 4, 99, 100 };
    cout << solve(A) << endl;
}

入力

{ 2, 3, 4, 99, 100 }

出力

2

計算量

ソートに O(n log n)、ソート後の隣接要素の走査に O(n) の計算量がかかるため、全体の時間計算量は O(n log n) となります。入力の配列をそのままソートする場合は、追加のメモリはほぼ不要で、空間計算量は O(1) です。