C++で解く！レーティングが重複しないチームメンバーのインデックス列を見つけるプログラム

要素数 n の配列 A と数値 k が与えられたとします。クラスには n 人の生徒がおり、i 番目の生徒のレーティングは A[i] で表されます。ここで、「全メンバーのレーティングが互いに異なる」という条件を満たす k 人のチームを編成することを目標とします。編成が不可能な場合は「Impossible」を返し、可能な場合は選んだ生徒のインデックス列を返してください。

例えば、入力が A = [15, 13, 15, 15, 12]、k = 3 の場合、出力は [1, 2, 5] となります。これは、1番目・2番目・5番目の生徒のレーティングがそれぞれ 15・13・12 であり、互いに重複していないためです。

解法のアプローチ

この問題は、配列を先頭から走査し、「そのレーティングの値がまだ一度も現れていない」要素だけを選んでいくことで解けます。具体的な考え方は以下の通りです。

• 各レーティングの出現済みフラグを管理する配列 app を用意します。
• 選択した生徒のインデックスを格納する配列 ans を用意します。
• 先頭から順に走査し、初めて登場するレーティングを持つ要素のインデックスを ans に記録していきます。
• 最終的に記録できた人数（重複なしの人数）が k 以上であれば、ans の先頭から k 個を出力します。k 未満であれば、十分な人数を集められないため「Impossible」となります。

アルゴリズムの手順

この問題を解くために、以下のステップに従います。

app と ans という2つの大きな配列を定義し、0で初期化する
cnt := 0
n := A のサイズ
i := 1 から n まで、i を1ずつ増やしながら繰り返す：
    a := A[i - 1]
    もし app[a] が 0 ならば：
        app[a] を1増やす
        cnt を1増やす
        ans[cnt] := i
もし cnt >= k ならば：
    i := 1 から k まで、i を1ずつ増やしながら繰り返す：
        ans[i] を出力する
そうでなければ：
    「Impossible」を返す

C++による実装例

理解を深めるために、以下の実装例を見てみましょう。

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

void solve(vector<int> A, int k) {
    int app[101] = { 0 }, ans[101] = { 0 }, cnt = 0;
    int n = A.size();
    for (int i = 1; i <= n; i++) {
        int a = A[i - 1];
        if (!app[a]) {
            app[a]++;
            ans[++cnt] = i;
        }
    }
    if (cnt >= k) {
        for (int i = 1; i <= k; i++)
            cout << ans[i] << ", ";
    }
    else
        cout << "Impossible";
}
int main() {
    vector<int> A = { 15, 13, 15, 15, 12 };
    int k = 3;
    solve(A, k);
}

入力

{ 15, 13, 15, 15, 12 }, 3

出力

1, 2, 5,

計算量と注意点

このアルゴリズムは配列を一度走査するだけでよいため、時間計算量は O(n)、空間計算量は固定サイズの補助配列を使用する O(1) となります。

ただし、この実装では補助配列のサイズを101としているため、レーティングの値が 1 以上 100 以下であることが前提となっています。レーティングの範囲がそれより広い場合は、配列の代わりに unordered_set や map などの連想コンテナを使うことで、任意の整数値に対応できるようになります。