C++でカードを捨てた後の最小合計を求める方法

問題概要

配列Tに5つの数値が格納されているとします。5枚のカードがあり、i番目のカードにはT[i]という数字が書かれています。一部のカードを捨てることができ、目的は残ったカードに書かれた数字の合計を最小化することです。

ただし、同じ数字が書かれた2枚または3枚のカードを捨てる操作は、最大1回までしか行えません。同じ数字のカードを2枚または3枚選べない場合は、カードを捨てません。このとき、実現可能な最小の合計を求める必要があります。

例えば、入力が T = [7, 3, 7, 3, 20] の場合、出力は 26 になります。これは「7」が書かれた2枚のカードを捨てることで、残りの合計が 3 + 3 + 20 = 26 となるためです。

解法のアプローチ

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

1. 配列Tの全要素の合計mを計算し、同時に各数字の出現回数をサイズ101のカウント配列kに記録します。
2. 出現回数が2回以上の数字iについて、その数字をmin(3, k[i])枚捨てた場合の合計「m − i × min(3, k[i])」を候補として計算します。
3. 元の合計mとすべての候補を比較し、最小値Mを返します。

n := 5
m := 0
サイズ101の配列kを定義し、0で初期化
for initialize i := 0, when i < n, update (increase i by 1), do:
    a := T[i]
    m := m + a
    (increase k[a] by 1)
M := m
for initialize i := 0, when i < 101, update (increase i by 1), do:
    if k[i] > 1, then:
        M := minimum of M and (m - i * (minimum of 3 and k[i]))
return M

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> T)
{
    int n = 5, m = 0, a;
    int k[101] = { 0 };
    for (int i = 0; i < n; i++)
    {
        int a = T[i];
        m += a;
        k[a]++;
    }
    int M = m;
    for (int i = 0; i < 101; i++)
        if (k[i] > 1)
        {
            M = min(M, m - i * (min(3, k[i])));
        }
    return M;
}
int main()
{
    vector<int> T = { 7, 3, 7, 3, 20 };
    cout << solve(T) << endl;
}

入力

{ 7, 3, 7, 3, 20 }

出力

26

まとめ

このアルゴリズムの計算量はO(n)であり、非常に効率的です。ポイントは、同じ数字のカードを捨てることで得られる削減効果を、各数字ごとに一度だけ評価することです。min(3, k[i])を使うことで、2枚または3枚のどちらを捨てた場合により多く合計を減らせるかを自動的に判断しています。