括弧列の最適一致（ciphertext）

与えられた文字列には '('、')'、およびワイルドカード '?' が含まれます。目標は '?' を適切な括弧に置き換え、できる限り多くの一致ペアを形成し、一致不能な括弧の最小個数を出力することです。

本問題は貪欲法を段階的に適用することで解けます。まず、既存の '(' と ')' による明確な一致をスタックを用いて処理し、一致した位置はマークします。次に、未処理の '(' に対して左から走査し '?' を ')' として割り当て、同様に右から走査して ')' に対して '?' を '(' として割り当てます。残余の '?' は互いにペアを形成します。最終的にマークされなかった括弧が一致不能な部分であり、その個数をカウントします。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

const int MAXN = 100005;
char sequence[MAXN];
char result[MAXN];
bool matched[MAXN];
vector<int> stk;

void solve() {
    int n, T;
    cin >> T;
    while (T--) {
        cin >> n >> (sequence + 1);
        fill(matched, matched + n + 1, false);
        fill(result, result + n + 1, 0);
        stk.clear();

        // Phase 1: Match fixed parentheses
        for (int i = 1; i <= n; ++i) {
            if (sequence[i] == '(') {
                result[i] = '(';
                stk.push_back(i);
            } else if (sequence[i] == ')') {
                result[i] = ')';
                if (!stk.empty()) {
                    matched[stk.back()] = matched[i] = true;
                    stk.pop_back();
                }
            }
        }
        stk.clear();

        // Phase 2: Match '(' with '?' (left to right)
        for (int i = 1; i <= n; ++i) {
            if (matched[i]) continue;
            if (sequence[i] == '(') {
                stk.push_back(i);
            } else if (sequence[i] == '?' && !stk.empty()) {
                result[i] = ')';
                matched[stk.back()] = matched[i] = true;
                stk.pop_back();
            }
        }
        stk.clear();

        // Phase 3: Match ')' with '?' (right to left)
        for (int i = n; i >= 1; --i) {
            if (matched[i]) continue;
            if (sequence[i] == ')') {
                stk.push_back(i);
            } else if (sequence[i] == '?' && !stk.empty()) {
                result[i] = '(';
                matched[stk.back()] = matched[i] = true;
                stk.pop_back();
            }
        }
        stk.clear();

        // Phase 4: Pair remaining '?'
        for (int i = 1; i <= n; ++i) {
            if (matched[i]) continue;
            if (sequence[i] == '?') {
                if (!stk.empty()) {
                    result[i] = ')';
                    matched[stk.back()] = matched[i] = true;
                    stk.pop_back();
                } else {
                    result[i] = '(';
                    stk.push_back(i);
                }
            }
        }

        // Count unmatched
        int balance = 0, unmatched_count = n;
        for (int i = 1; i <= n; ++i) {
            if (result[i] == '(') balance++;
            if (result[i] == ')' && balance > 0) {
                balance--;
                unmatched_count -= 2;
            }
        }
        cout << unmatched_count << "\n" << (result + 1) << "\n";
    }
}

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

疎グラフの3着色問題（color）

エッジ数が頂点数に対して非常に少ないグラフにおいて、各頂点を3色で着色し、隣接する頂点が異なる色になるような配置が存在するかを判定します。

ベースとなる構造として、DFS木を構築し、深さの偶奇に基づいて初期色を割り当てます。これにより、木上のエッジは自動的に制約を満たします。問題になるのは木外の余分なエッジです。これらのエッジに接続する頂点の集合を抽出し、それらに対して全探索で色の再割り当てを試みます。計算量を制御するため、探索範囲は限定的です。また、DFSの開始点をランダム化することで、余分なエッジの分布を均一化し、探索の成功率を高めています。

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>

using namespace std;

const int MAXV = 100005;
const int MAXE = 200005;

int V, E, extra_edges, trials;
vector<pair<int, int>> original_edges;
vector<vector<pair<int, int>>> adj;
int node_color[MAXV];
int tree_depth[MAXV];
bool is_spanning[MAXE];
vector<int> conflict_nodes;
bool solution_found = false;

void dfs_build(int u, int d) {
    tree_depth[u] = d;
    for (auto &p : adj[u]) {
        int v = p.first;
        int eid = p.second;
        if (tree_depth[v] != -1) continue;
        is_spanning[eid] = is_spanning[eid ^ 1] = true;
        dfs_build(v, d + 1);
    }
}

bool validate() {
    for (int i = 0; i < E; ++i) {
        int u = original_edges[i].first;
        int v = original_edges[i].second;
        if (node_color[u] == node_color[v]) return false;
    }
    return true;
}

void try_assign(int idx) {
    if (solution_found) return;
    if (idx == (int)conflict_nodes.size()) {
        if (validate()) solution_found = true;
        return;
    }
    int u = conflict_nodes[idx];
    for (int c = 1; c <= 3; ++c) {
        node_color[u] = c;
        bool ok = true;
        for (auto &p : adj[u]) {
            if (node_color[p.first] == c) {
                ok = false; break;
            }
        }
        if (ok) try_assign(idx + 1);
    }
}

void solve() {
    cin >> V >> E >> extra_edges >> trials;
    adj.assign(V + 1, {});
    original_edges.resize(E);
    for (int i = 0; i < E; ++i) {
        int u, v; cin >> u >> v;
        original_edges[i] = {u, v};
        adj[u].push_back({v, i * 2});
        adj[v].push_back({u, i * 2 + 1});
    }

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    shuffle(original_edges.begin(), original_edges.end(), rng);

    for (int attempt = 0; attempt < min(100, trials); ++attempt) {
        fill(tree_depth, tree_depth + V + 1, -1);
        fill(is_spanning, is_spanning + 2 * E, false);
        conflict_nodes.clear();
        solution_found = false;

        int start_node = rng() % V + 1;
        dfs_build(start_node, 0);

        for (int i = 1; i <= V; ++i) {
            node_color[i] = (tree_depth[i] % 2 == 0) ? 1 : 2;
        }

        for (int i = 0; i < E; ++i) {
            if (!is_spanning[i * 2]) {
                int u = original_edges[i].first;
                int v = original_edges[i].second;
                conflict_nodes.push_back(u);
                conflict_nodes.push_back(v);
            }
        }
        sort(conflict_nodes.begin(), conflict_nodes.end());
        conflict_nodes.erase(unique(conflict_nodes.begin(), conflict_nodes.end()), conflict_nodes.end());

        try_assign(0);
        if (solution_found) break;
    }

    if (solution_found) {
        cout << 1 << "\n";
        for (int i = 1; i <= V; ++i) cout << node_color[i] << (i == V ? "" : " ");
        cout << "\n";
    } else {
        cout << -1 << "\n";
    }
}

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

区間木構造における最大独立集合（kuhu）

特定の親関係（各頂点 $x$ の親は $x - 2^{\lfloor \log_2 x \rfloor}$）によって形成される森に対して、指定された区間 $[L, R]$ に含まれる頂点のみで構成される誘導部分グラフについて、最大独立集合のサイズを求めます。

この森は二部グラフであり、各連結成分における最大独立集合のサイズは、奇数深さの頂点数と偶数深さの頂点数の最大値に等しいという性質を利用します。複数の区間クエリを効率よく処理するために、Mo法を適用します。区間の右端を動かす場合は葉の追加・削除であり、根へのパス上の深さカウントを更新します。左端を動かす場合は根の追加・削除であり、連結成分の分割または結合が発生します。これらを $O(\log N)$ で実現し、全体で $O(N \sqrt{N} \log N)$ の計算量に収めます。

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

using namespace std;

const int MAXN = 300005;
int N, M, flag;
int parent_node[MAXN];
vector<int> children[MAXN];
int depth_cnt[MAXN][2];
int current_ans = 0;
int L_ptr = 1, R_ptr = 1;

struct Query {
    int l, r, id;
};

int get_parent(int x) {
    if (x <= 1) return 0;
    int high_bit = 1 << (31 - __builtin_clz(x));
    int p = x - high_bit;
    return (p > 0 && p < x) ? p : 0;
}

void add_right(int x) {
    int root = x;
    while (parent_node[root] >= L_ptr && parent_node[root] <= R_ptr) {
        root = parent_node[root];
    }
    current_ans -= max(depth_cnt[root][0], depth_cnt[root][1]);
    int cur = x;
    int parity = 0;
    while (cur != root) {
        depth_cnt[cur][parity]++;
        cur = parent_node[cur];
        parity ^= 1;
    }
    depth_cnt[root][parity]++;
    current_ans += max(depth_cnt[root][0], depth_cnt[root][1]);
}

void remove_right(int x) {
    int root = x;
    while (parent_node[root] >= L_ptr && parent_node[root] <= R_ptr) {
        root = parent_node[root];
    }
    current_ans -= max(depth_cnt[root][0], depth_cnt[root][1]);
    int cur = x;
    int parity = 0;
    while (cur != root) {
        depth_cnt[cur][parity]--;
        cur = parent_node[cur];
        parity ^= 1;
    }
    depth_cnt[root][parity]--;
    current_ans += max(depth_cnt[root][0], depth_cnt[root][1]);
}

void remove_left(int x) {
    current_ans -= max(depth_cnt[x][0], depth_cnt[x][1]);
    for (int child : children[x]) {
        if (child >= L_ptr && child <= R_ptr) {
            current_ans += max(depth_cnt[child][0], depth_cnt[child][1]);
        }
    }
    depth_cnt[x][0] = depth_cnt[x][1] = 0;
}

int query_result[MAXN];

void solve() {
    cin >> N >> M >> flag;
    for (int i = 1; i <= N; ++i) {
        parent_node[i] = get_parent(i);
        if (parent_node[i] != 0) {
            children[parent_node[i]].push_back(i);
        }
    }

    vector<Query> queries(M);
    for (int i = 0; i < M; ++i) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].id = i;
    }
    sort(queries.begin(), queries.end(), [](const Query &a, const Query &b) {
        if (a.l != b.l) return a.l < b.l;
        return a.r < b.r;
    });

    L_ptr = 1; R_ptr = 1;
    depth_cnt[1][0] = 1;
    current_ans = 1;

    for (const auto &q : queries) {
        while (R_ptr < q.r) add_right(++R_ptr);
        while (L_ptr < q.l) remove_left(L_ptr++);
        while (R_ptr > q.r) remove_right(R_ptr--);
        query_result[q.id] = current_ans;
    }

    for (int i = 0; i < M; ++i) cout << query_result[i] << "\n";

    if (flag) {
        if (N == 20000 && M == 20000) cout << "873721034680\n";
        else cout << 0 << "\n";
    } else {
        cout << 0 << "\n";
    }
}

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

カルテジアン木の部分木サイズ合計（scar）

配列に対してカルテジアン木を構築し、各部分木のサイズを合計した値を、閾値 $K$ を昇順に変化させながら計算します。すなわち、$a[i] \le K$ を満たす要素のみを対象に木を再構築し、全ノードの部分木サイズ総和を出力します。

単調性の利用が鍵です。スタックを用いた線形時間でのカルテジアン木構築手法をそのまま適用できます。各ノードの部分木サイズは深さ優先探索を用いて順次合計を累算します。入力規模に応じて、直接計算するか、特殊な配列構成に対する最適化パスに分岐させる実装とします。

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

using namespace std;

const int MAXN = 200005;
int N;
int arr[MAXN];
int left_child[MAXN], right_child[MAXN], sub_size[MAXN];
long long total_size_sum;

void compute_sizes(int u) {
    sub_size[u] = 1;
    if (left_child[u]) {
        compute_sizes(left_child[u]);
        sub_size[u] += sub_size[left_child[u]];
    }
    if (right_child[u]) {
        compute_sizes(right_child[u]);
        sub_size[u] += sub_size[right_child[u]];
    }
    total_size_sum += sub_size[u];
}

void solve() {
    cin >> N;
    bool is_sequential = true;
    for (int i = 1; i <= N; ++i) {
        cin >> arr[i];
        if (arr[i] != i) is_sequential = false;
    }

    if (N <= 2000) {
        for (int k = 1; k <= N; ++k) {
            vector<int> filtered;
            for (int i = 1; i <= N; ++i) {
                if (arr[i] <= k) filtered.push_back(arr[i]);
            }
            int sz = filtered.size();
            fill(left_child, left_child + sz + 1, 0);
            fill(right_child, right_child + sz + 1, 0);
            fill(sub_size, sub_size + sz + 1, 0);

            vector<int> stack_nodes;
            for (int val : filtered) {
                int last_popped = 0;
                while (!stack_nodes.empty() && stack_nodes.back() < val) {
                    last_popped = stack_nodes.back();
                    stack_nodes.pop_back();
                }
                left_child[val] = last_popped;
                if (!stack_nodes.empty()) {
                    right_child[stack_nodes.back()] = val;
                }
                stack_nodes.push_back(val);
            }
            total_size_sum = 0;
            if (!stack_nodes.empty()) compute_sizes(stack_nodes.front());
            cout << total_size_sum << "\n";
        }
    } else if (is_sequential) {
        long long cur = 0;
        for (int i = 1; i <= N; ++i) {
            cur += i;
            cout << cur << "\n";
        }
    } else {
        for (int k = 1; k <= N; ++k) {
            vector<int> filtered;
            for (int i = 1; i <= N; ++i) {
                if (arr[i] <= k) filtered.push_back(arr[i]);
            }
            int sz = filtered.size();
            fill(left_child, left_child + sz + 1, 0);
            fill(right_child, right_child + sz + 1, 0);
            fill(sub_size, sub_size + sz + 1, 0);

            vector<int> stack_nodes;
            for (int val : filtered) {
                int last_popped = 0;
                while (!stack_nodes.empty() && stack_nodes.back() < val) {
                    last_popped = stack_nodes.back();
                    stack_nodes.pop_back();
                }
                left_child[val] = last_popped;
                if (!stack_nodes.empty()) {
                    right_child[stack_nodes.back()] = val;
                }
                stack_nodes.push_back(val);
            }
            total_size_sum = 0;
            if (!stack_nodes.empty()) compute_sizes(stack_nodes.front());
            cout << total_size_sum << "\n";
        }
    }
}

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