C++で目標値を満たすために丸め誤差を最小化する方法

問題の概要

価格の配列 P = [p1, p2, ..., pn] と目標値(target)が与えられます。各価格 Pi を Floor(Pi)(切り捨て)または Ceil(Pi)(切り上げ)のどちらかで丸め、丸め後の配列 [Round1(P1), Round2(P2), ..., Roundn(Pn)] の合計がちょうど目標値になるようにしてください。

どのような丸め方をしても合計を目標値にできない場合は、文字列 "-1" を返します。達成できる場合は、丸め誤差の総和が最小となる値を返します。丸め誤差は次の式で定義され、小数点以下3桁の文字列として出力します。

Σ |Roundi(Pi) − Pi|(i = 1 〜 n)

具体例で確認する

入力が ["0.700", "2.800", "4.900"]、目標値が 8 のケースを考えてみましょう。

• 0.700 → 0(切り捨て)
• 2.800 → 3(切り上げ)
• 4.900 → 5(切り上げ)

丸め後の合計は 0 + 3 + 5 = 8 となり、目標値を満たします。このときの誤差は次のように計算できます。

(0.7 − 0) + (3 − 2.8) + (5 − 4.9) = 0.7 + 0.2 + 0.1 = 1.000

解法の考え方

この問題は貪欲法と優先度付きキュー(priority queue)を組み合わせることで効率的に解けます。ポイントは次の通りです。

• まずすべて切り捨てる: 全ての価格を一旦 Floor で丸めた状態を基準にします。このときの累積誤差を ret、目標値との差分を target として管理します。
• 切り上げコストを記録する: 小数部を持つ価格について、「Floor から Ceil に変更したときに誤差がどれだけ増減するか」を diff = (high − x) − (x − low) として計算し、優先度付きキューに格納します。元の値が整数に近いほど diff は小さくなり、切り上げしても誤差がほとんど増えません。
• 必要な回数だけ切り上げる: target の回数だけ、キューから diff が最小の要素を取り出して ret に加算します。これにより、合計を目標値に合わせながら誤差を最小化できます。
• 不可能性の判定: 切り上げ可能な要素数(pq のサイズ)より target が大きい場合、または target が負の場合は "-1" を返します。

アルゴリズムの手順

1. ret := 0 と初期化する。
2. double 型用の比較関数を持つ優先度付きキュー pq を用意する。
3. i を 0 から prices のサイズ未満まで繰り返す。
   • x := prices[i] を double に変換した値
   • low := floor(x)、high := ceil(x)
   • low ≠ high の場合(小数部を持つ場合):
     • diff := (high − x) − (x − low)
     • diff を pq に挿入する
   • target := target − low
   • ret := ret + (x − low)
4. target > pq.size() または target < 0 なら "-1" を返す。
5. target が 0 になるまで次を繰り返す。
   • ret := ret + pq.top() とし、pq から先頭を削除する。
   • target を 1 減らす。
6. ret を文字列化し、小数点以下3桁までの部分文字列を返す。

計算量は、各要素のキュー操作が対数時間であるため、全体で O(n log n) となります。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
struct Comparator{
    bool operator()(double a, double b) {
        return !(a < b);
    }
};
class Solution {
    public:
    string minimizeError(vector<string>& prices, int target) {
        double ret = 0;
        priority_queue < double, vector < double >, Comparator > pq;
        for(int i = 0; i < prices.size(); i++){
            double x = stod(prices[i]);
            double low = floor(x);
            double high = ceil(x);
            if(low != high){
                double diff = ((high - x) - (x - low));
                pq.push(diff);
            }
            target -= low;
            ret += (x - low);
        }
        if(target > pq.size() || target < 0) return "-1";
        while(target--){
            ret += pq.top();
            pq.pop();
        }
        string s = to_string (ret);
        return s.substr (0, s.find_first_of ('.', 0) + 4);
    }
};
main(){
    vector<string> v = {"0.700","2.800","4.900"};
    Solution ob;
    cout << (ob.minimizeError(v, 8));
}

入力

["0.700","2.800","4.900"]
8

出力

"1.000"

実装のポイント

Comparator 構造体では operator() をオーバーロードし、!(a < b) を返すことで最小ヒープ(min-heap)として動作させています。これにより、pq.top() が常に「切り上げに切り替えたときの追加誤差が最も小さい要素」を返すようになります。

また、出力時には to_string で生成した文字列に対して find_first_of で小数点の位置を特定し、その位置 + 4 文字(小数点を含めて3桁)までを substr で切り出しています。これにより "1.000" のような固定小数点形式の文字列が得られます。