問題A: 双方向関係の検出

与えられた順列pにおいて、異なるインデックスi, jが互いを参照し合っているか（つまり p[i] = j 且つ p[j] = i）を判定する。そのようなペアが存在する場合、必要な選択肢の数は2であり、存在しない場合は必ず3必要となる。全探索ではなく配列への直接アクセスにより、線形時間でこの条件を満たすかどうかをチェックできる。

#include <iostream>
#include <vector>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> p(n + 1);
    for (int i = 1; i <= n; ++i) cin >> p[i];

    bool found_cycle = false;
    for (int i = 1; i <= n; ++i) {
        int target = p[i];
        if (target > i && p[target] == i) {
            found_cycle = true;
            break;
        }
    }
    cout << (found_cycle ? 2 : 3) << '\n';
}

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

問題B: 連続ブロックの移動コスト最適化

バイナリ文字列に含まれる「1」の連続部分を対象に、右端まで移動させるための最小コストを求める。特定の長さを持つ連続ブロックを右隣の空白領域へジャンプさせる際のコストは常にブロック長 + 1で一定である。したがって、文字列をスキャンして各ブロックの始点と終点を特定し、次の障害物または文字列末端に到達するまで、移動可能な分だけ段階的にコストを加算していく貪欲戦略で最適解が得られる。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
using ll = long long;

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    ll total_cost = 0;
    
    for (int start = 0; start < n; ) {
        if (s[start] != '1') {
            start++;
            continue;
        }
        int end = start;
        while (end + 1 < n && s[end + 1] == '1') end++;
        
        ll block_len = end - start + 1;
        // ブロックを右に移动する際に、次に到達できない地点までシミュレート
        int current_r = end;
        while (current_r < n - 1) {
            total_cost += block_len + 1;
            current_r++;
        }
        start = end + 1;
    }
    cout << total_cost << '\n';
}

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

問題C: 区間最小値置換DP

制約 k ≤ 10 が小さいことを活用する。この問題は「長さ k 以下の連続部分列を1つ選び、その全区間を最小値で置き換える」という操作を適度に実行して数列の総和を最小化する問題と言い換えられる。

dp[i] をi番目までの要素を処理した後の最小合計値とする。現在注目している位置 i を区間の右端とする場合、左端 j を i から後ろへ最大 k 步まで遡りながら区間の最小値 mn を維持し、遷移を行う。計算量は状態数が N、遷移の探索幅が K であるため O(NK) で実行可能だ。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1e18;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    vector<ll> dp(n + 1, 0);
    for (int i = 1; i <= n; ++i) dp[i] = dp[i - 1] + a[i];

    for (int i = 1; i <= n; ++i) {
        ll mn = a[i];
        for (int l = 0; l < k && i - l - 1 >= 0; ++l) {
            mn = min(mn, a[i - l]);
            int prev_idx = i - l - 1;
            ll candidate = dp[prev_idx] + mn * (l + 1);
            if (candidate < dp[i]) dp[i] = candidate;
        }
    }
    cout << dp[n] << '\n';
}

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

問題D: ソート・優先度付きキュー・累積和を用いた戦略的選択

プレイヤーAとBの交互選択ゲームを解析する。Bは定数 k 個のアイテムを選ぶが、その戦略は評価値 b[i] の高いものから優先的であることが確定する。Aはそれ以外のすべてのアイテムを取得する。

b[i] によってアイテムを昇順にソートし、Bが選ぶ範囲の閾値 x を固定することを考える。
1. x 以上の範囲から、Aの負担 a[i] が小さい k 個をBが取る。これは最大ヒープ（優先度付きキュー）で動態管理する。
2. x より下の範囲では、b[i] - a[i] ≥ 0 ならばAが有利になるため、その差分を累積和の前計算で保持しておき、O(1) で加算する。
両者を組み合わせて各閾値におけるAの利益を最大化し、全体で O(N log N) に収める。

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
using ll = long long;

struct Element { ll a, b, id; };

void solve() {
    int n;
    ll k;
    cin >> n >> k;
    vector<Element> elems(n);
    for (int i = 0; i < n; ++i) {
        cin >> elems[i].a;
        elems[i].id = i;
    }
    for (int i = 0; i < n; ++i) cin >> elems[i].b;

    sort(elems.begin(), elems.end(), [](const Element& x, const Element& y) {
        return x.b < y.b;
    });

    vector<ll> pref_sum(n, 0);
    for (int i = 0; i < n; ++i) {
        pref_sum[i] = pref_sum[i - 1] + max(0LL, elems[i].b - elems[i].a);
    }

    priority_queue<ll> max_heap_a;
    ll current_b_load = 0;
    ll max_advantage = -1;

    for (int i = n - 1; i >= 0; --i) {
        max_heap_a.push(elems[i].a);
        current_b_load += elems[i].a;
        if (max_heap_a.size() > k) {
            current_b_load -= max_heap_a.top();
            max_heap_a.pop();
        }
        if (max_heap_a.size() == k) {
            ll a_gain = pref_sum[i - 1] - current_b_load;
            if (a_gain > max_advantage) max_advantage = a_gain;
        }
    }
    cout << max_advantage << '\n';
}

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

問題E: セグメント木による有効範囲の動的管理

同一値が連続出現するインデックス i と、それまでに出現した直近の位置 l およびさらに前の位置 lt の関係性を利用する。位置 i に着目した時、有効な左端の範囲は連続した区間で定義され、範囲外に出ると同時に無効化する必要がある。

これをシークエンス上でスキャンするには、「区間の加減算」と「全域最小値の監視」が可能データ構造が求められる。セグメント木を実装し、初期状態で全インデックスに1を付与してから、各要素の登場ごとに旧有効範囲の减算と新有効範囲の加算を行う。木根ノードの値が0に達した瞬間、対応する要素が条件を満たせなくなるためカウントを増やし、範囲を再設定する。このアプローチにより O(N log N) の時間計算量で処理を完了できる。

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

template <typename T>
struct SegmentTree {
    int sz;
    vector<T> tree, lazy;
    SegmentTree(int n) : sz(1) {
        while (sz < n) sz *= 2;
        tree.assign(2 * sz, 0);
        lazy.assign(2 * sz, 0);
    }
    void push(int node) {
        if (lazy[node] != 0) {
            tree[2 * node] += lazy[node]; lazy[2 * node] += lazy[node];
            tree[2 * node + 1] += lazy[node]; lazy[2 * node + 1] += lazy[node];
            lazy[node] = 0;
        }
    }
    void range_add(int ql, int qr, T val, int node=1, int l=0, int r=-1) {
        if (r < 0) r = sz - 1;
        if (ql > r || qr < l) return;
        if (ql <= l && r <= qr) { tree[node] += val; lazy[node] += val; return; }
        push(node);
        int mid = (l + r) / 2;
        range_add(ql, qr, val, 2 * node, l, mid);
        range_add(ql, qr, val, 2 * node + 1, mid + 1, r);
        tree[node] = min(tree[2 * node], tree[2 * node + 1]);
    }
    T get_min_root() { return tree[1]; }
};

void solve() {
    int n;
    cin >> n;
    SegmentTree<ll> seg(n);
    seg.range_add(0, n - 1, 1);

    vector<int> last_pos(n, -2);
    vector<int> cur_pos(n, -1);
    ll answer = 0;

    for (int i = 0; i < n; ++i) {
        int val; cin >> val;
        // 既存の有効範囲を無効化
        if (last_pos[val] + 1 <= cur_pos[val])
            seg.range_add(last_pos[val] + 1, cur_pos[val], -1);
        // 新しい有効範囲を付与
        if (cur_pos[val] + 1 < i)
            seg.range_add(cur_pos[val] + 1, i - 1, 1);

        last_pos[val] = cur_pos[val];
        cur_pos[val] = i;

        if (seg.get_min_root() == 0) {
            answer++;
            seg.range_add(0, i, 1);
        }
    }
    cout << answer << '\n';
}

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