C++で解く「パッチ配列」問題 ― 貪欲法で最小の追加要素数を求める

問題の概要

配列 nums と整数 n が与えられたとします。配列に要素を追加（パッチ）することで、範囲 [1, n]（両端を含む）内の任意の整数が、配列内のいくつかの要素の総和として表せるようにしたいと考えます。このとき、必要な追加要素（パッチ）の最小個数を求めるのが本問題です。

たとえば、配列が [1, 4]、n = 7 の場合、答えは 1 になります。初期状態では、部分集合の和として 1、4、5 しか作れません。しかし 2 を配列に追加すると、部分集合は [1]、[2]、[4]、[1,2]、[1,4]、[2,4]、[1,2,4] となり、その総和は順に 1、2、4、3、5、6、7 となって、1〜7 のすべての整数を表現できるようになります。

解法のアプローチ（貪欲法）

以下の手順で解きます。

• req := 1、i := 0、ret := 0 で初期化します。

• req <= n の間、次を繰り返します。

  • i が nums のサイズ未満 かつ nums[i] <= req の場合：

    • req = req + nums[i]

    • i を 1 増やす

  • それ以外の場合：

    • req = req + req（req を2倍する）

    • ret を 1 増やす（パッチを1つ追加）

• 最後に ret を返します。

なぜこの貪欲法が有効なのか

変数 req は「現在の配列の要素だけですでに構築できる連続区間 [1, req) の上限」を表しています。

• nums[i] <= req ならば、既存の区間に nums[i] を組み合わせることで、表現可能な範囲を [1, req + nums[i]) まで拡張できます。
• そうでない場合（次の要素が大きすぎる、または配列を使い切った場合）、req 自体が作れないため、req を新しいパッチとして追加する必要があります。これにより表現可能な範囲は [1, 2×req) まで倍増し、ret をインクリメントします。

各ループで i が進むか req が倍増するため、計算量は O(m + log n)（m は配列の長さ）と非常に効率的です。また、req は繰り返し2倍されて int の最大値を超える可能性があるため、オーバーフロー防止の観点から long long 型を使用している点にも注目してください。

C++ 実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int minPatches(vector<int>& nums, int n) {
        long long int req = 1;
        int i = 0;
        int ret = 0;
        while(req <= n){
            if(i < nums.size() && nums[i] <= req){
                req += nums[i];
                i++;
            } else {
                req += req;
                ret++;
            }
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,4};
    cout << (ob.minPatches(v, 7));
}

入力

{1,4}

出力

1