問題A：数値の置換と減少による合計値制御

配列の各要素に対して「任意の要素を1減算する」または「任意の要素を他の要素の値へコピーする」操作を繰り返し、配列総和を閾値K以下にするための最小操作回数を求める問題です。

効率的な解法は貪欲法と累積和の組み合わせです。まず配列を昇順ソートします。大きな値を直接減算するよりも、最小値へコピーした方が一度に合計値を大きく削減できるため、後ろからi個の要素を最小値に置き換えるパターンを全探索します。このとき、配列前半の累積和に置き換えた要素数分の最小値を加算すれば、置換後の総和がO(1)で算出可能です。総和がKを超えている場合は、残りを減算操作で処理します。既に最小値に揃えられた要素群（元の最小値を含む計i+1個）を均等に減算するのが最適であり、必要な減算回数は剰余を考慮した切り上げ計算で求められます。各iにおける総操作回数を記録し、その最小値を出力します。

#include <iostream>
#include <vector>
#include <algorithm>

using std::cin, std::cout, std::vector, std::sort, std::min;
using ll = long long;

void run_case() {
    int n; ll limit;
    cin >> n >> limit;
    vector<ll> vals(n);
    for (auto &v : vals) cin >> v;

    sort(vals.begin(), vals.end());

    vector<ll> pref(n);
    pref[0] = vals[0];
    for (int idx = 1; idx < n; ++idx)
        pref[idx] = pref[idx - 1] + vals[idx];

    ll best_ops = -1;

    for (int replaced = 0; replaced < n; ++replaced) {
        ll current_sum = pref[n - replaced - 1] + vals[0] * replaced;
        ll ops = replaced;
        if (current_sum > limit) {
            ll diff = current_sum - limit;
            ll dec_needed = (diff + replaced) / (replaced + 1);
            ops += dec_needed;
        }
        if (best_ops == -1 || ops < best_ops) best_ops = ops;
    }
    cout << best_ops << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t; cin >> t;
    while (t--) run_case();
    return 0;
}

問題E：特定紙幣による複数金額の最小枚数構成

面額が1, 2, 3の3種類の紙幣を用いて、N個の指定金額を全て支払い可能にするとき、使用する紙幣の総枚数を最小化する問題です。

面額3の紙幣を優先して使用するのが基本方針です。面額1は高々1枚、面額2は高々2枚しか必要ありません（それ以上使用する場合、より高額の紙幣や他の組み合わせで代替可能です）。この性質を利用し、面額1と2の使用枚数を固定した上で全探索を行います。各対象金額に対して、固定した1と2の枚数範囲内で残りを面額3で賄う場合の必要枚数を計算し、全金額の中で最大となる値を取り出します。この最大値に固定枚数を加えたものが総使用枚数であり、探索空間内の最小値を求めます。

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using std::cin, std::cout, std::vector, std::min, std::max;
using ll = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        int m; cin >> m;
        vector<int> targets(m);
        for (auto &x : targets) cin >> x;

        ll min_total = INT_MAX;
        for (int c1 = 0; c1 <= 1; ++c1) {
            for (int c2 = 0; c2 <= 2; ++c2) {
                ll max_v3 = 0;
                for (int val : targets) {
                    ll req = INT_MAX;
                    for (int u1 = 0; u1 <= c1; ++u1) {
                        for (int u2 = 0; u2 <= c2; ++u2) {
                            ll rem = val - u1 - 2 * u2;
                            if (rem >= 0 && rem % 3 == 0)
                                req = min(req, rem / 3);
                        }
                    }
                    max_v3 = max(max_v3, req);
                }
                min_total = min(min_total, max_v3 + c1 + c2);
            }
        }
        cout << min_total << '\n';
    }
    return 0;
}

問題F：シーケンスに対するオフライン更新と置換処理

データ列への末尾追加と、列内の全要素に対する一斉置換を繰り返し実行した後の最終状態を出力する問題です。

前方から処理すると置換操作ごとに配列全体を走査する必要が生じ、計算量が膨張します。代わりに、クエリを逆順に処理するオフライン手法を採用します。各数値が最終的にどの値に落ち着くかを管理するマッピング配列を用意し、末尾のクエリから順に評価します。逆順処理において追加操作に遭遇した場合は、現在のマッピング値を結果リストに記録します。置換操作（xをyに置き換える）の場合は、マッピングを`map[x] = map[y]`のように更新します。これにより、過去の変換が後続の置換に連鎖的に反映されるため、O(1)で正確な最終値を取得できます。記録したリストを逆順に出力することで、元の順序のデータ列が復元されます。

#include <iostream>
#include <vector>
#include <numeric>

using std::cin, std::cout, std::vector, std::iota;

struct Query {
    int type;
    int val_a, val_b;
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int q; cin >> q;
    vector<Query> history(q + 1);
    for (int i = 1; i <= q; ++i) {
        cin >> history[i].type;
        if (history[i].type == 1) {
            cin >> history[i].val_a;
        } else {
            cin >> history[i].val_a >> history[i].val_b;
        }
    }

    vector<int> mapping(500005);
    iota(mapping.begin(), mapping.end(), 0);

    vector<int> result;
    result.reserve(q);
    for (int i = q; i >= 1; --i) {
        if (history[i].type == 1) {
            result.push_back(mapping[history[i].val_a]);
        } else {
            mapping[history[i].val_a] = mapping[history[i].val_b];
        }
    }

    for (int i = result.size() - 1; i >= 0; --i) {
        cout << result[i] << (i == 0 ? '\n' : ' ');
    }
    return 0;
}

問題G：矩形辺上の点を用いた最大面積三角形の構成

長方形の各辺上に複数の点が配置されているとき、これらの中から3点を選んで面積が最大となる三角形を求める問題です。

三角形の面積は「底辺×高さ÷2」で定義されます。矩形の辺上に配置された点を底辺とした場合、高さは矩形の対辺間の距離（幅または高さ）で固定されます。したがって、各辺において存在する点の最大座標と最小座標の差（すなわちその辺上の最大底辺長）を算出し、対応する矩形の寸法（幅または高さ）を乗算すれば面積が得られます。4つの辺全てについてこの計算を行い、得られた面積の最大値を出力します。

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using std::cin, std::cout, std::vector, std::max, std::min;
using ll = long long;

void execute() {
    ll rect_w, rect_h;
    cin >> rect_w >> rect_h;
    ll optimal = 0;
    ll heights[] = {rect_h, rect_h, rect_w, rect_w};

    for (int edge = 0; edge < 4; ++edge) {
        int point_count;
        cin >> point_count;
        ll min_pos = LLONG_MAX, max_pos = LLONG_MIN;
        for (int i = 0; i < point_count; ++i) {
            ll pos;
            cin >> pos;
            min_pos = min(min_pos, pos);
            max_pos = max(max_pos, pos);
        }
        ll current_area = (max_pos - min_pos) * heights[edge];
        optimal = max(optimal, current_area);
    }
    cout << optimal << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int cases;
    cin >> cases;
    while (cases--) execute();
    return 0;
}