A. Vasya and Book

現在のページ x から目的のページ y まで、1回の操作で d ページ進むか戻る（ただし範囲外には行けない）ときの最小操作回数を求める。

以下の3通りを検討し、可能なものの最小値を取る：

1. |x - y| が d で割り切れる場合：直接移動可能。回数は |x - y| / d。
2. 先頭ページ（1）経由： (y - 1) % d == 0 のとき、x → 1 → y の合計回数は ceil(x / d) + (y - 1) / d。
3. 末尾ページ（n）経由： (n - y) % d == 0 のとき、x → n → y の合計回数は ceil((n - x) / d) + (n - y) / d。

いずれも不可能なら -1 を出力する。

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

void solve() {
    int n, x, y, d;
    cin >> n >> x >> y >> d;

    const int INF = 1e9;
    int ans = INF;

    if (abs(x - y) % d == 0)
        ans = min(ans, abs(x - y) / d);

    if ((y - 1) % d == 0)
        ans = min(ans, (x + d - 1) / d + (y - 1) / d);

    if ((n - y) % d == 0)
        ans = min(ans, (n - x + d - 1) / d + (n - y) / d);

    cout << (ans == INF ? -1 : ans) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) solve();
}

B. Vova and Trophies

文字列中の 'G' を最大限連続させる問題。1つの 'S' を別の 'G' と交換できる（実際には位置を入れ替えるのではなく、1つの 'S' を 'G' に置き換えられるイメージ）。

前処理として、各位置までの左側連続 'G' 数（pre）と右側連続 'G' 数（suf）を計算。各 'S' の位置で左右の 'G' を連結し、全体の 'G' 数が余っていれば +1 できる。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    string s; cin >> s;
    s = " " + s;

    vector<int> pre(n + 1), suf(n + 2);
    int totalG = 0, maxLen = 0;

    for (int i = 1; i <= n; ++i) {
        if (s[i] == 'G') {
            pre[i] = pre[i-1] + 1;
            totalG++;
            maxLen = max(maxLen, pre[i]);
        }
    }
    for (int i = n; i >= 1; --i) {
        if (s[i] == 'G') suf[i] = suf[i+1] + 1;
    }

    for (int i = 1; i <= n; ++i) {
        if (s[i] == 'S') {
            int merged = pre[i-1] + suf[i+1];
            if (merged < totalG) merged++;
            maxLen = max(maxLen, merged);
        }
    }

    cout << maxLen << '\n';
}

C. Multi-Subject Competition

複数の科目ごとに学生のスキル値が与えられ、各科目から同じ人数 k を選んで合計スコアを最大化する。ただし、各科目の選んだ学生のスコア合計が正でなければならない。

各科目のスキル値を降順ソートし、累積和を計算。累積和が正である限り、その k に対する総和に加算。全 k について最大値を取る。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector<vector<i64>> groups(m);
    for (int i = 0; i < n; ++i) {
        int s, r; cin >> s >> r;
        groups[s-1].push_back(r);
    }

    vector<i64> total(n, 0);
    for (auto& v : groups) {
        if (v.empty()) continue;
        sort(v.rbegin(), v.rend());
        for (int i = 0; i < v.size(); ++i) {
            if (i > 0) v[i] += v[i-1];
            if (v[i] > 0) total[i] += v[i];
            else break;
        }
    }

    cout << *max_element(total.begin(), total.end()) << '\n';
}

D. Maximum Diameter Graph

各頂点の次数上限が与えられたとき、連結グラフを作成し、直径を最大化する。

まず、総次数が 2*(n-1) 以上でなければ不可能。次に、次数 ≥2 の頂点を主鎖として並べる。その後、次数1の葉を主鎖の両端に優先的に接続（直径を伸ばすため）。残りの葉は主鎖内の空き次数に接続。

最終的な直径は「主鎖の長さ + 両端に接続した葉の数 - 1」。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<int> deg(n);
    int sum = 0;
    for (int& d : deg) {
        cin >> d;
        sum += d;
    }

    if (sum < 2 * (n - 1)) {
        cout << "NO\n";
        return 0;
    }

    vector<pair<int, int>> core;
    vector<int> leaves;
    for (int i = 0; i < n; ++i) {
        if (deg[i] == 1) leaves.push_back(i);
        else core.push_back({deg[i], i});
    }

    vector<vector<bool>> adj(n, vector<bool>(n));
    int diameter = (int)core.size();

    if (core.size() > 1) {
        sort(core.begin(), core.end(), greater<>());
        for (int i = 0; i + 1 < core.size(); ++i) {
            int u = core[i].second, v = core[i+1].second;
            adj[u][v] = adj[v][u] = true;
            deg[u]--; deg[v]--;
        }
    }

    // 葉を両端に接続
    for (int idx : {0, (int)core.size() - 1}) {
        if (leaves.empty()) break;
        if (idx < 0 || idx >= core.size()) continue;
        int v = core[idx].second;
        if (deg[v] > 0) {
            int leaf = leaves.back(); leaves.pop_back();
            adj[v][leaf] = adj[leaf][v] = true;
            deg[v]--;
            diameter++;
        }
    }

    // 残りの葉を内部に接続
    for (auto& [_, v] : core) {
        while (deg[v] > 0 && !leaves.empty()) {
            int leaf = leaves.back(); leaves.pop_back();
            adj[v][leaf] = adj[leaf][v] = true;
            deg[v]--;
        }
    }

    cout << "YES " << diameter - 1 << '\n';
    vector<pair<int, int>> edges;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (adj[i][j]) edges.emplace_back(i + 1, j + 1);

    cout << edges.size() << '\n';
    for (auto& [u, v] : edges) cout << u << ' ' << v << '\n';
}

E. Increasing Frequency

配列中の特定の値 c の出現頻度を、ある区間を選び、その区間内で任意の値 x に一括変更することで最大化する。

各位置 j について、x の出現数と c の出現数の差分を前から追跡。各 x について、過去の最小差分を記録し、現在の差分との差が「その区間で x に変更すると得られる増分」となる。

最終的な答えは、元の c の個数 + 最大増分。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, c; cin >> n >> c;
    vector<int> a(n);
    for (int& x : a) cin >> x;

    unordered_map<int, int> cnt, minDiff;
    int base = 0, bestGain = 0;

    for (int x : a) {
        if (x == c) base++;
        cnt[x]++;
        int diff = cnt[x] - cnt[c];
        minDiff[x] = min(minDiff[x], diff - (x == c ? 1 : 0)); // 実際は diff を更新前に使う
        // 正しくは：minDiff[x] は diff 更新前の最小値
    }

    // 再計算
    cnt.clear();
    minDiff.clear();
    for (int x : a) {
        minDiff[x] = min(minDiff[x], cnt[x] - cnt[c]);
        cnt[x]++;
        int gain = (cnt[x] - cnt[c]) - minDiff[x];
        bestGain = max(bestGain, gain);
    }

    cout << base + bestGain << '\n';
}