最大評価値となる部品セットを見つけるC++プログラム

問題文

あるメーカーが特定の製品向けに部品を製造しているとします。このメーカーは n 種類の異なる部品を保有しており、各部品は3つの基準で評価されます。n 個の部品の評価は配列 ratings として与えられ、各要素は (A, B, C) という形式で表されます。ここで A、B、C はそれぞれ異なる評価基準のスコアです。

さて、ある OEM(相手先ブランド製造企業)が、このメーカーから自社製品のために m 個の部品を購入したいと考えています。OEM は以下の条件を満たす部品を選択します。

• 同じ部品を2個以上購入してはならない。

• V = |Aの評価値の合計| + |Bの評価値の合計| + |Cの評価値の合計| となる V が最大になるように、部品のセットを選ぶ。

OEM が選択できる部品の中から得られる V の最大値を求めるのがこの問題の目的です。

例えば、入力が n = 6、m = 4、ratings = {{2, 3, 5}, {3, 5, 2}, {4, 8, 5}, {1, 5, 3}, {7, 2, 7}, {4, 3, 6}} の場合、出力は 56 になります。

OEM が部品1、3、5、6 を選択した場合、各カテゴリの評価値の合計は次のようになります。

カテゴリA = 2 + 4 + 7 + 4 = 17
カテゴリB = 3 + 8 + 2 + 3 = 16
カテゴリC = 5 + 5 + 7 + 6 = 23
V の合計値は 17 + 16 + 23 = 56 となります。

解法のアプローチ

この問題のポイントは絶対値の扱いです。任意の値 x に対して |x| = max(x, −x) が成り立つことを利用すると、V は「A、B、C の合計値それぞれに + または − の符号を付けた8通りの組み合わせ」のうちのいずれか1つと必ず一致します。そこで、部品ごとにすべての符号パターン(±A ±B ±C)の値をあらかじめ計算しておき、各パターンごとに降順ソートして上位 m 個の合計を求め、その中で最大のものを答えとすればよいのです。

具体的な手順は以下の通りです。

1. 各部品 i について、8つの符号パターン(a+b+c、a−b−c、a+b−c、a−b+c、−a+b+c、−a−b−c、−a+b−c、−a−b+c)の値を配列 arr に格納する。
2. 各行(各符号パターン)を昇順にソートした後、逆順に並べ替えて降順にする。
3. m = 0 であれば V = 0 とする。そうでなければ、各行の上位 m 個の合計 k を求め、現在の V と比較して大きい方で V を更新する。
4. V を返す。

N := 100
サイズ 9 x N の配列 arr を定義
配列 ans を定義
i := 0 から n 未満の間、繰り返し:
    a := ratings[i] の1番目の値
    b := ratings[i] の2番目の値
    c := ratings[i] の3番目の値
    arr[1, i] := a + b + c
    arr[2, i] := a - b - c
    arr[3, i] := a + b - c
    arr[4, i] := a - b + c
    arr[5, i] := -a + b + c
    arr[6, i] := -a - b - c
    arr[7, i] := -a + b - c
    arr[8, i] := -a - b + c
i := 1 から 8 以下の間、繰り返し:
    配列 arr[i] をソートする
i := 1 から 8 以下の間、繰り返し:
    配列 arr[i] を逆順にする
m が 0 と等しい場合:
    V := 0
それ以外の場合:
    j := 1 から 8 以下の間、繰り返し:
        k := 0
        i := 0 から m 未満の間、繰り返し:
            k := k + arr[j, i]
            V := V と k の最大値
V を返す

計算量

8つの符号パターンそれぞれに対してソートを行うため、時間計算量は O(n log n)、空間計算量は O(n) となります。

実装例(C++)

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

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int modval = (int) 1e9 + 7;
#define N 100
int solve(int n, int m, vector<tuple<int, int, int>> ratings) {
   int V, arr[9][N];
   vector<int> ans;
   for(int i = 0; i < n; i++) {
      int a, b, c;
      tie(a, b, c) = ratings[i];
      arr[1][i] = a + b + c;
      arr[2][i] = a - b - c;
      arr[3][i] = a + b - c;
      arr[4][i] = a - b + c;
      arr[5][i] = -a + b + c;
      arr[6][i] = -a - b - c;
      arr[7][i] = -a + b - c;
      arr[8][i] = -a - b + c;
   }
   for(int i = 1; i <= 8; i++)
    sort(arr[i], arr[i] + n);
   for(int i = 1; i <= 8; i++)
    reverse(arr[i], arr[i] + n);
   if (m == 0)
   V = 0;
   else {
      for (int j = 1; j <= 8; j++) {
         int k = 0;
         for (int i = 0; i < m; i++)
            k += arr[j][i];
         V = max(V, k);
      }
   }
   return V;
}
int main() {
   int n = 6, m = 4;
   vector<tuple<int, int, int>> ratings = {{2, 3, 5}, {3, 5, 2}, {4, 8, 5}, {1, 5, 3}, {7, 2, 7}, {4, 3, 6}};
   cout<< solve(n, m, ratings);
   return 0;
}

入力

6, 4, {{2, 3, 5}, {3, 5, 2}, {4, 8, 5}, {1, 5, 3}, {7, 2, 7}, {4, 3, 6}}

出力

56