基本的な比較計算

二つの整数の積を比較する問題では、直接的な計算を用いる。

#include <iostream>
int main() {
    long long w, x, y, z;
    std::cin >> w >> x >> y >> z;
    std::cout << (w * x < y * z ? "First" : "Second") << '\n';
    return 0;
}

数値精度の比較

長さ最大2×10⁵の文字列で与えられる小数を、小数点以下6桁まで比較する。整数部分は小数として扱い、精度を保証する。

#include <string>
#include <iostream>

std::string ensurePrecision(const std::string& num) {
    std::string temp = num;
    if(temp.find('.') == std::string::npos) temp += '.';
    temp += "000000";
    return temp.substr(0, temp.find('.') + 7);
}

int main() {
    std::string numA, numB;
    std::cin >> numA >> numB;
    std::cout << (ensurePrecision(numA) == ensurePrecision(numB) ? "EQUAL" : "DIFF") << '\n';
    return 0;
}

グリッドの接続性解析

2×nグリッドにおいて、隣接セルの連結性をグラフとして捉え、切断点（関節点）を特定する。孤立点は特別に扱う。

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

const int MAX_N = 1000010;
vector<int> graph[MAX_N];
int discovery[MAX_N], low[MAX_N], timer = 0;
bool isCritical[MAX_N];

void dfs(int node, int parent) {
    discovery[node] = low[node] = ++timer;
    int childCount = 0;
    for(int neighbor : graph[node]) {
        if(neighbor == parent) continue;
        if(!discovery[neighbor]) {
            childCount++;
            dfs(neighbor, node);
            low[node] = min(low[node], low[neighbor]);
            if(low[neighbor] >= discovery[node] && parent != -1) {
                isCritical[node] = true;
            }
        } else {
            low[node] = min(low[node], discovery[neighbor]);
        }
    }
    if(parent == -1 && childCount > 1) isCritical[node] = true;
}

int main() {
    int cols;
    cin >> cols;
    string rowA, rowB;
    cin >> rowA >> rowB;
    int totalCells = 2 * cols;
    for(int r = 0; r < 2; ++r) {
        for(int c = 0; c < cols; ++c) {
            if((r == 0 ? rowA[c] : rowB[c]) == '.') continue;
            int currentId = r * cols + c;
            bool isolated = true;
            int dr[] = {0, 0, 1, -1};
            int dc[] = {1, -1, 0, 0};
            for(int dir = 0; dir < 4; ++dir) {
                int nr = r + dr[dir], nc = c + dc[dir];
                if(nr >= 0 && nr < 2 && nc >= 0 && nc < cols) {
                    char neighborChar = (nr == 0 ? rowA[nc] : rowB[nc]);
                    if(neighborChar == 'x') continue;
                    int neighborId = nr * cols + nc;
                    graph[currentId].push_back(neighborId);
                    isolated = false;
                }
            }
            if(isolated) totalCells--;
        }
    }
    for(int i = 0; i < 2 * cols; ++i) {
        if(!discovery[i]) dfs(i, -1);
    }
    for(int i = 0; i < 2 * cols; ++i) {
        if(isCritical[i]) totalCells++;
    }
    cout << totalCells << '\n';
    return 0;
}

連結成分の最適な色変換

グラフの各連結成分において、最も多い色に統一するのが最適である。変更数は成分サイズから最大色の出現数を引いた値となる。

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

int main() {
    int vertices, edges;
    cin >> vertices >> edges;
    vector<int> colors(vertices + 1);
    for(int i = 1; i <= vertices; ++i) cin >> colors[i];
    vector adjList(vertices + 1);
    for(int i = 0; i < edges; ++i) {
        int u, v;
        cin >> u >> v;
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }
    vector<bool> visited(vertices + 1, false);
    auto processComponent = [&](int start) -> int {
        unordered_map colorFreq;
        queue<int> q;
        q.push(start);
        visited[start] = true;
        int componentSize = 0;
        int maxFreq = 0;
        while(!q.empty()) {
            int current = q.front(); q.pop();
            componentSize++;
            colorFreq[colors[current]]++;
            maxFreq = max(maxFreq, colorFreq[colors[current]]);
            for(int neighbor : adjList[current]) {
                if(!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        return componentSize - maxFreq;
    };
    int totalCost = 0;
    for(int i = 1; i <= vertices; ++i) {
        if(!visited[i]) {
            totalCost += processComponent(i);
        }
    }
    cout << totalCost << '\n';
    return 0;
}

括弧ペアの削除順序

スタックを用いて各括弧ペアに番号を割り当て、削除不可能な開き括弧の数を記録することで効率的に計算する。

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

int main() {
    int n;
    cin >> n;
    string seq;
    cin >> seq;
    seq = " " + seq;
    vector<int> pairId(2 * n + 1, 0);
    vector<int> cannotRemove(n + 1, 0);
    stack<int> posStack;
    int currentPair = 0;
    for(int i = 1; i <= 2 * n; ++i) {
        if(seq[i] == '(') {
            posStack.push(i);
            pairId[i] = ++currentPair;
        } else {
            if(posStack.empty()) {
                cout << "-1\n";
                return 0;
            }
            int openPos = posStack.top();
            posStack.pop();
            pairId[i] = pairId[openPos];
            cannotRemove[pairId[openPos]] = posStack.size();
        }
    }
    for(int i = 1; i <= n; ++i) {
        cout << n - cannotRemove[i] << (i == n ? "\n" : " ");
    }
    return 0;
}

特殊な数列の区間クエリ処理

セグメント木を用いて区間積と特殊な累積和を効率的に管理する。更新は等比数列の和で計算する。

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

const long long MOD = 1000000007;

struct ModNum {
    long long val;
    ModNum(long long v = 0) : val(v % MOD) {}
    ModNum operator*(ModNum other) const { return ModNum(val * other.val % MOD); }
    ModNum operator+(ModNum other) const { return ModNum((val + other.val) % MOD); }
    ModNum operator-(ModNum other) const { return ModNum((val - other.val + MOD) % MOD); }
    ModNum power(long long exp) const {
        ModNum result(1), base = *this;
        while(exp > 0) {
            if(exp & 1) result = result * base;
            base = base * base;
            exp >>= 1;
        }
        return result;
    }
    ModNum inverse() const { return power(MOD - 2); }
    ModNum operator/(ModNum other) const { return *this * other.inverse(); }
};

struct SegmentNode {
    int left, right;
    ModNum product;
    ModNum specialSum;
    ModNum lazy;
    SegmentNode() : left(0), right(0), product(1), specialSum(0), lazy(0) {}
};

class SegmentTree {
    vector<SegmentNode> tree;
    int n;
    void applyLazy(int idx, ModNum value) {
        int length = tree[idx].right - tree[idx].left + 1;
        tree[idx].lazy = value;
        tree[idx].product = value.power(length);
        if(value.val == 1) {
            tree[idx].specialSum = ModNum(length);
        } else {
            tree[idx].specialSum = (value.power(length + 1) - value) / (value - ModNum(1));
        }
    }
    void pushDown(int idx) {
        if(tree[idx].lazy.val != 0) {
            applyLazy(idx * 2, tree[idx].lazy);
            applyLazy(idx * 2 + 1, tree[idx].lazy);
            tree[idx].lazy = ModNum(0);
        }
    }
    void combine(SegmentNode& parent, const SegmentNode& leftChild, const SegmentNode& rightChild) {
        parent.product = leftChild.product * rightChild.product;
        parent.specialSum = leftChild.specialSum + leftChild.product * rightChild.specialSum;
    }
public:
    SegmentTree(const vector<int>& arr) : n(arr.size() - 1) {
        tree.resize(4 * n + 5);
        function build = [&](int idx, int l, int r) {
            tree[idx].left = l; tree[idx].right = r;
            tree[idx].lazy = ModNum(0);
            if(l == r) {
                ModNum val(arr[l]);
                tree[idx].product = val;
                tree[idx].specialSum = val;
                return;
            }
            int mid = (l + r) / 2;
            build(idx * 2, l, mid);
            build(idx * 2 + 1, mid + 1, r);
            combine(tree[idx], tree[idx * 2], tree[idx * 2 + 1]);
        };
        build(1, 1, n);
    }
    void rangeUpdate(int idx, int ql, int qr, ModNum value) {
        if(tree[idx].left > qr || tree[idx].right < ql) return;
        if(tree[idx].left >= ql && tree[idx].right <= qr) {
            applyLazy(idx, value);
            return;
        }
        pushDown(idx);
        rangeUpdate(idx * 2, ql, qr, value);
        rangeUpdate(idx * 2 + 1, ql, qr, value);
        combine(tree[idx], tree[idx * 2], tree[idx * 2 + 1]);
    }
    SegmentNode rangeQuery(int idx, int ql, int qr) {
        if(tree[idx].left >= ql && tree[idx].right <= qr) return tree[idx];
        pushDown(idx);
        int mid = (tree[idx].left + tree[idx].right) / 2;
        if(qr <= mid) return rangeQuery(idx * 2, ql, qr);
        if(ql > mid) return rangeQuery(idx * 2 + 1, ql, qr);
        SegmentNode leftResult = rangeQuery(idx * 2, ql, qr);
        SegmentNode rightResult = rangeQuery(idx * 2 + 1, ql, qr);
        SegmentNode merged;
        merged.left = ql; merged.right = qr;
        combine(merged, leftResult, rightResult);
        return merged;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int size, queries;
    cin >> size >> queries;
    vector<int> initial(size + 1);
    for(int i = 1; i <= size; ++i) cin >> initial[i];
    SegmentTree seg(initial);
    while(queries--) {
        int type;
        cin >> type;
        if(type == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            seg.rangeUpdate(1, l, r, ModNum(x));
        } else {
            int l, r;
            cin >> l >> r;
            cout << seg.rangeQuery(1, l, r).specialSum.val << '\n';
        }
    }
    return 0;
}