問題A: 分割和の最適化

本問は、指定された条件を満たす配列の最大要素を最小化する数学的なパターン認識問題です。要素数 \(n\) と目標値 \(k\) の大小関係に応じて、計算量を \(O(1)\) に抑える直接的な処理が可能です。

• \(n > k\) の場合: 要素数が目標値を上回るため、配列の各位置に \(1\) を配置することで条件を満たせます。\(n\) が \(k\) で割り切れる場合は最大値を \(1\) とできます。余りが生じる場合は、余りを分散させるために最大値が \(2\) になります。
• \(n \leq k\) の場合: 要素数が少ないため、値を均等に配分する必要があります。ベースとなる値は \(k / n\) となり、割り切れずに端数が残る場合は最大値に \(1\) を加算して切り上げ処理を行います。

#include <iostream>
#include <cmath>

using namespace std;

void solve() {
    long long itemCount, divisor;
    cin >> itemCount >> divisor;

    if (itemCount > divisor) {
        cout << (itemCount % divisor == 0 ? 1 : 2) << '\n';
    } else {
        cout << (divisor / itemCount + (divisor % itemCount != 0)) << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int testCases;
    cin >> testCases;
    while (testCases--) {
        solve();
    }
    return 0;
}

問題B: インフレーションシミュレーション

この問題は貪欲法による順次処理が適用できます。各要素について、その値が直前の累積和に対する指定割合 \(k\) を超えないように監視します。条件を満たさない場合は、直前の累積和に最小限の値を追加して閾値を引き上げ、その追加量を累積していきます。浮動小数点演算による精度問題を避けるため、整数算術を用いた切り上げ処理を採用します。

#include <iostream>
#include <vector>

using namespace std;

void processCase() {
    int size;
    long long limit;
    cin >> size >> limit;

    vector<long long> data(size);
    for (auto &val : data) cin >> val;

    long long totalAdded = 0;
    long long prefixSum = 0;

    for (int idx = 1; idx < size; ++idx) {
        prefixSum += data[idx - 1];
        long long requiredBase = (data[idx] * 100 + limit - 1) / limit;

        if (prefixSum < requiredBase) {
            long long diff = requiredBase - prefixSum;
            totalAdded += diff;
            prefixSum += diff;
        }
    }
    cout << totalAdded << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;
    while (q--) {
        processCase();
    }
    return 0;
}

問題C: 最長単純サイクルの探索

動的計画法を用いて、各連結点における最大サイクル長を逐次的に更新します。状態 \(dp[i]\) を、\(i\) 番目のセグメントまでを使用した際に形成可能な最大のサイクル長と定義します。遷移ロジックは以下の2通りに分類されます。

• 両端の接続位置が一致する場合 (\(a[i] = b[i]\)): 現在セグメントのみで独立した閉路が形成されるため、長さは \(c[i] + 1\) となります。
• 接続位置が一致しない場合: 直前のサイクルを延長して活用するか、現在セグメントの両端間の差分を活用して新規閉路を構築するかを比較します。最適な経路長に現在のセグメント長と接続点分を加算して状態を更新します。

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

using namespace std;

void runTest() {
    int m;
    cin >> m;

    vector<int> segLen(m), leftConn(m), rightConn(m);
    for (auto &x : segLen) cin >> x;
    for (auto &x : leftConn) cin >> x;
    for (auto &x : rightConn) cin >> x;

    vector<int> dp(m, 0);
    int maxCycle = 0;

    for (int i = 1; i < m; ++i) {
        int diff = abs(leftConn[i] - rightConn[i]);
        if (diff == 0) {
            dp[i] = segLen[i] + 1;
        } else {
            dp[i] = max(diff, dp[i - 1] - diff) + segLen[i] + 1;
        }
        maxCycle = max(maxCycle, dp[i]);
    }
    cout << maxCycle << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        runTest();
    }
    return 0;
}