C. メッセンジャープログラム

2つの配列aとb、および整数Lが与えられます。aとbのインデックスのシーケンスpを見つけて、\(\sum a_{p_i} + \sum |b_{p_i}-b_{p_{i+1}}| \leq L\)を満たす必要があります。

解法

キー1：bを昇順にソートすることが最適です。

キー2：固定された\(b_l\)と\(b_r\)に対して、\(\sum^r_l |b_{p_i}-b_{p_{i+1}}| = b_r - b_l\)となり、これは固定値なので、中間のa_iとb_iを任意に削除できます。必要なのは\(\sum a \leq L - (b_r - b_l)\)だけです。

lを固定し、左から右へ拡張します。優先度キューを使って現在のaの最大値を維持し、合計が超えた場合は最大要素を削除します。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve() {
    int n, L;
    cin >> n >> L;
    vector<pair<int, int>> arr(n);
    for (int i = 0; i < n; ++i)
        cin >> arr[i].second >> arr[i].first; // first: b, second: a

    sort(arr.begin(), arr.end());
    int result = 0;
    for (int left = 0; left < n; ++left) {
        priority_queue<int> pq;
        int total = 0;
        for (int right = left; right < n; ++right) {
            pq.push(arr[right].second);
            total += arr[right].second;
            while (!pq.empty() && total > L - (arr[right].first - arr[left].first)) {
                total -= pq.top();
                pq.pop();
            }
            result = max(result, static_cast<int>(pq.size()));
        }
    }

    cout << result << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

時間計算量：O(n^2 log n)

D. 試験問題

集合sと正整数cが与えられ、0からcまでの範囲で(x, y)ペアの個数を求めます。条件はx + y ∉ sかつy - x ∉ sです。

解法

直接的に条件を満たすx, yを計算するのは困難です。しかし、すべての場合から不適切なケースを引くことで解決できます。

すべての場合の数は\(C^{2}_{n+2}\)（具体的な組み合わせを考えてみてください）です。

仮定として、x + y = t ∈ sの場合、その場合の数は(t / 2 + 1)となります。同様に、y - x = t ∈ sの場合、その場合の数は(c - t + 1)となります。ただし、これらの二つの状況には重複があります。例えば、1 + 2 = 3と2 - 1 = 1のように、両方の条件で同じペアが考慮されることがあります。

この重複を避けるため、奇数と偶数のグループに分割します。重複するケースは必ず一方のグループから選ばれます。

最終的な答えは以下のようになります： [ ans = C^{2}{n+2} - \sum{\forall t \in S} (t/2 + 1) - \sum_{\forall t \in S} (c - t + 1) + C^{2}* + C^{2}* + n ]

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve() {
    int n, c;
    cin >> n >> c;
    int odd = 0, even = 0;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
        if (nums[i] % 2) odd++;
        else even++;
    }

    int result = (c + 1) * (c + 2) / 2;
    for (int i = 0; i < n; ++i) {
        result -= nums[i] / 2 + 1;
        result -= (c - nums[i] + 1);
    }
    result += (odd * (odd - 1)) / 2 + (even * (even - 1)) / 2;
    result += n;
    cout << result << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}