問題1: 農場の統一された牛群

各要素の前後で最初に現れる同一要素の位置をprevおよびnext配列で管理します。区間[l, r]が有効となる条件は、next[l] > rかつprev[r] < lを満たすことです。

左端点lを固定し、右端点の有効性をセグメント木で管理します。prev[r] < lを満たすrを二重ポインタで追跡しながら、セグメント木の対応位置をインクリメントします。各lでの解は、セグメント木の区間[l, next[l]-1]の総和から1を引いた値です。

計算量はO(n log n)で実現可能です。

#include <bits/stdc++.h>
using namespace std;
constexpr int MAX = 1e5 + 5;

class SegmentTree {
    vector<int> tree;
    int size;
public:
    SegmentTree(int n) : size(n), tree(n * 4) {}
    void update(int idx, int val, int node = 1, int l = 1, int r = size) {
        if (l == r) { tree[node] += val; return; }
        int mid = (l + r) / 2;
        if (idx <= mid) update(idx, val, node * 2, l, mid);
        else update(idx, val, node * 2 + 1, mid + 1, r);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
    int query(int ql, int qr, int node = 1, int l = 1, int r = size) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) / 2;
        return query(ql, qr, node * 2, l, mid) + 
               query(ql, qr, node * 2 + 1, mid + 1, r);
    }
};

int main() {
    int n; cin >> n;
    vector<int> arr(n + 1), prev(n + 1), next(n + 1), last(MAX);
    
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        prev[i] = last[arr[i]];
        last[arr[i]] = i;
    }
    
    fill(last.begin(), last.end(), n + 1);
    for (int i = n; i >= 1; i--) {
        next[i] = last[arr[i]];
        last[arr[i]] = i;
    }

    vector<pair<int, int>> candidates;
    for (int i = 1; i <= n; i++) 
        candidates.emplace_back(prev[i], i);
    sort(candidates.begin(), candidates.end());

    SegmentTree seg(n);
    long long ans = 0;
    int ptr = 0;
    
    for (int l = 1; l <= n; l++) {
        while (ptr < n && candidates[ptr].first < l) {
            seg.update(candidates[ptr].second, 1);
            ptr++;
        }
        ans += seg.query(l + 1, next[l] - 1);
    }
    cout << ans << endl;
}

問題2: ポータルネットワーク

ポータル間の接続関係をグラフでモデル化すると、互いに到達可能なポータル群は閉路を形成します。操作の本質は、2つの閉路を1つに結合することにあります。

この問題をUnion-Findデータ構造を用いた最小全域木の構築問題に帰着できます。各操作を辺とみなし、コスト昇順に処理して連結成分を統合します。最終的に得られる木の総コストが解となります。

#include <bits/stdc++.h>
using namespace std;
constexpr int MAX = 2e5 + 5;

struct UnionFind {
    vector<int> parent;
    UnionFind(int n) : parent(n + 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    bool merge(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return false;
        parent[b] = a;
        return true;
    }
};

int main() {
    int n; cin >> n;
    vector<array<int, 4>> portals(n + 1);
    vector<tuple<int, int, int>> edges;
    
    for (int i = 1; i <= n; i++) {
        int cost, a, b, c, d;
        cin >> cost >> a >> b >> c >> d;
        portals[i] = {a, b, c, d};
        edges.emplace_back(cost, a, c);
        edges.emplace_back(cost, b, d);
    }

    UnionFind uf(2 * n);
    for (int i = 1; i <= n; i++) {
        uf.merge(portals[i][0], portals[i][1]);
        uf.merge(portals[i][2], portals[i][3]);
    }

    sort(edges.begin(), edges.end());
    long long total = 0;
    
    for (auto [cost, u, v] : edges) {
        if (uf.merge(u, v)) total += cost;
    }
    cout << total << endl;
}

問題3: 頂点配置の数え上げ

三角形の外周を構成する3頂点(i,j,k)に注目し、動的計画法の状態をdp[len][i][j][k]で定義します。ここでlenは現在の頂点数、i,j,kは外周三角形の頂点インデックスです。

状態遷移では2パターンを考慮します：

1. 外周に新しい頂点を追加：三角形(i,j,k)の内部にあり、追加可能か面積法で判定
2. 内部に頂点を追加：sum - len + 1通りの選択肢（sumは現在の三角形内部の頂点総数）

頂点インデックスの順序を常に昇順に保つことで、状態の重複を回避します。計算量はO(N⁵)ですが、定数倍が小さい実装で現実的な実行時間となります。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int MAX = 55;
const ll MOD = 1e9 + 7;

ll dp[MAX][MAX][MAX][MAX];
int x[MAX], y[MAX], n;

ll cross(int a, int b, int c) {
    return 1LL * (x[b] - x[a]) * (y[c] - y[a]) - 
           1LL * (x[c] - x[a]) * (y[b] - y[a]);
}

bool inside(int i, int j, int k, int p) {
    ll area = abs(cross(i, j, k));
    return area == abs(cross(i, j, p)) + 
                 abs(cross(j, k, p)) + 
                 abs(cross(k, i, p));
}

void normalize(int& a, int& b, int& c) {
    if (a > b) swap(a, b);
    if (a > c) swap(a, c);
    if (b > c) swap(b, c);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) 
        cin >> x[i] >> y[i];

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            for (int k = j + 1; k <= n; k++) {
                dp[3][i][j][k] = 6;
            }
        }
    }

    for (int len = 4; len <= n; len++) {
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                for (int k = j + 1; k <= n; k++) {
                    int count = 0;
                    for (int p = 1; p <= n; p++) {
                        if (p == i || p == j || p == k) continue;
                        if (!inside(i, j, k, p)) continue;
                        
                        count++;
                        int a = i, b = j, c = p;
                        normalize(a, b, c);
                        dp[len][i][j][k] = (dp[len][i][j][k] + dp[len-1][a][b][c]) % MOD;
                        
                        a = i, b = k, c = p;
                        normalize(a, b, c);
                        dp[len][i][j][k] = (dp[len][i][j][k] + dp[len-1][a][b][c]) % MOD;
                        
                        a = j, b = k, c = p;
                        normalize(a, b, c);
                        dp[len][i][j][k] = (dp[len][i][j][k] + dp[len-1][a][b][c]) % MOD;
                    }
                    dp[len][i][j][k] = (dp[len][i][j][k] + 
                        (count - len + 4) * dp[len-1][i][j][k]) % MOD;
                }
            }
        }
    }

    ll result = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            for (int k = j + 1; k <= n; k++)
                result = (result + dp[n][i][j][k]) % MOD;
    
    cout << result << endl;
}