AtCoder部 2026-03-18

2026年3月18日
AtCoder部

ABC372 D - Buildings

ビルを右から見ていく。 今見ているビルとの間に自分より高いビルがないようなビルをスタックで管理する。

int main() {
    int N;
    cin >> N;
    vector<int> H(N);
    for (int i = 0; i < N; i++) cin >> H[i];
    stack<int> st;
    st.push(H[N - 1]);
    vector<int> ans(N);
    for (int i = N - 2; i >= 0; i--) {
        ans[i] = st.size();
        while (!st.empty() && st.top() < H[i]) st.pop();
        st.push(H[i]);
    }
    print_list(ans);
}

ABC372 E - K-th Largest Connected Components

Union-Find。各連結成分に含まれる頂点をソートした列も追加で管理する。2つの連結成分をマージした結果この列の大きさが11以上になる場合、大きい方から10個だけのこす。

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<vector<int>> groups(N);
    for (int i = 0; i < N; i++) groups[i].push_back(i);
    dsu uf(N);
    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int u, v;
            cin >> u >> v;
            u--;
            v--;
            u = uf.leader(u);
            v = uf.leader(v);
            if (u != v) {
                vector<int> tmp(groups[u].size() + groups[v].size());
                merge(RALL(groups[u]), RALL(groups[v]), tmp.rbegin());
                int x = uf.merge(u, v);
                groups[x].clear();
                for (int i = 0; i < min((int)tmp.size(), 10); i++) groups[x].push_back(tmp[i]);
            }
        } else {
            int v, k;
            cin >> v >> k;
            v--;
            v = uf.leader(v);
            if (groups[v].size() >= k) {
                cout << groups[v][k - 1] + 1 << NL;
            } else {
                cout << -1 << NL;
            }
        }
    }
}

ABC369 D - Bonus EXP

dp[i][j]:=i匹目のモンスターまで見ていて、倒したモンスターの数%2がjのときの経験値の合計の最大値 という DP をする。

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    array<ll, 2> dp = {0, -INF};
    for (int i = 0; i < N; i++) {
        array<ll, 2> nxt = dp;
        chmax(nxt[0], dp[1] + 2 * A[i]);
        chmax(nxt[1], dp[0] + A[i]);
        dp = nxt;
    }
    cout << max(dp[0], dp[1]) << NL;
}
← All Posts