スキルレベルの異なる異動従業員の配分数を求めるC++プログラム

問題の概要

ある会社にはn人の従業員が在籍しており、各従業員はスキルに応じて1からkまでのいずれかのランクに分類されています。配列skillにはランクごとの従業員数が記録されており、skill[i]はランクiを持つ従業員の人数を表します。

ここで、会社に新しい支店が開設されることになり、さまざまなスキルを持つ従業員をそちらへ異動させることになりました。異動させる従業員の総数はm人です。今回の課題は、m人を適切に配置する方法を見つけ出し、次の式を最小化するような支店の従業員ランク配分表branchを求めることです。

最小化する式：max(branch[i]/m − skill[i]/n)

なお、branch[i]の値の合計はmに一致する必要があります。つまり、条件を満たすbranch[i]の各要素を具体的に求めることがゴールとなります。

例として、入力がk = 5、n = 10、m = 25、skill = {5, 3, 2, 7, 4}である場合、出力は「12 7 5 17 10」になります。

解法の手順

この問題は、比例配分で用いられる「最大剰余法（端数が大きい項目から優先的に切り上げる手法）」の考え方を使うと効率的に解けます。全体の流れは以下の通りです。

1. 各skill[i]に比率m/nを掛け、理論上の配分目標値を求めます。
2. 目標値の整数部分を取り出し、その合計をsumとして記録します。同時に、小数部分（剰余）とインデックスをペアにした配列aを作成します。
3. 配列aを小数部分の降順にソートし、逆順に並べ替えます。
4. 合計がmに届かない場合、小数部分が大きい順に対応するskill[i]へ1ずつ加算していきます。
5. 最終的な配分結果を出力します。

これを擬似コードで表すと次のようになります。

sum := 0
i を 0 から k-1 まで 1 ずつ増やしながら繰り返す:
   skill[i] := skill[i] * m / n
整数ペアを格納する配列 a を定義する
i を 0 から k-1 まで 1 ずつ増やしながら繰り返す:
   c := skill[i]
   sum := sum + c
   a[i] の第1要素 := skill[i] - c
   a[i] の第2要素 := i
配列 a をソートする
配列 a を逆順に並べ替える
i を 0 から m - sum - 1 まで 1 ずつ増やしながら繰り返す:
   skill[a[i] の第2要素] := skill[a[i] の第2要素] + 1
i を 0 から k-1 まで 1 ずつ増やしながら繰り返す:
   i が k - 1 と等しくなければ:
      skill[i] を出力
   そうでなければ:
      skill[i] を改行付きで出力

C++実装例

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

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

void solve(int k, int n, int m, vector<double> skill){
    int sum = 0;
    for (int i = 0; i < k; i++)
        skill[i] = skill[i] * m / n;
    vector<pair<double, int>> a(k);
    for (int i = 0; i < k; i++) {
        int c = skill[i];
        sum += c;
        a[i].first = skill[i] - c;
        a[i].second = i;
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    for (int i = 0; i < m - sum; i++) {
        skill[a[i].second] += 1;
    }
    for (int i = 0; i < k; i++) {
        if (i != k - 1)
            cout << int(skill[i]) << " ";
        else
            cout << int(skill[i]) << endl;
    }
}
int main() {
   int k = 5, n = 10, m = 25;
   vector<double> skill = {5, 3, 2, 7, 4};
   solve(k, n, m, skill);
   return 0;
}

入力

5, 10, 25, {5, 3, 2, 7, 4}

出力

12 7 5 17 10

まとめ

このプログラムは、比例配分の考え方に基づき、まず各ランクごとの理論値を計算したうえで、端数の大きいランクから順に不足分を配分することで、max(branch[i]/m − skill[i]/n) を最小化する配置を実現しています。処理時間はソートが支配的となるため計算量はO(k log k)であり、従業員数やランク数が増えても効率よく動作します。