ECR150-D Pairs of Segments

問題

Problem - D - Codeforces (diff: 2000)

区間の列 は次の条件を満たすとき、またそのときに限り「良い列」と呼ぶことにする。

• が偶数
• 共通区間を持つ要素同士に辺を張ったグラフを考えると、これが各連結成分のサイズがの個の連結成分になる

個の区間を与える。最小何個の区間を消去すれば良い列にすることが可能か求めよ

制約

• 
• 

解法

二つの共通区間を持つ二つの区間を全て列挙できる。これを一つの区間とみなすと区間スケジューリング問題に帰着する

実装

#include <bits/stdc++.h>

#include "Src/Template/IOSetting.hpp"
using namespace zawa;

bool Intersect(const std::pair<int, int>& i, const std::pair<int, int>& j) {
    return not (i.first < j.second or j.first < i.second);
}

// int brute(const std::vector<std::pair<int, int>>& RL) {
//     int n{(int)RL.size()};
//     int ans{n};
//     for (int bit{} ; bit < (1 << n) ; bit++) {
//         if (std::popcount((unsigned)bit) % 2) continue;
//         std::vector<int> use;
//         for (int i{} ; i < n ; i++) if (bit & (1 << i)) use.push_back(i);
//         std::vector<std::vector<int>> g(use.size());
//         for (int i{} ; i < (int)use.size() ; i++) {
//             for (int j{i + 1} ; j < (int)use.size() ; j++) {
//                 if (Intersect(RL[use[i]], RL[use[j]])) {
//                     g[i].emplace_back(j);
//                     g[j].emplace_back(i);
//                 }
//             }
//         }
//         std::vector<bool> vis(use.size());
//         int cnt{};
//         auto dfs{[&](auto dfs, int v) -> void {
//             cnt++;
//             vis[v] = true;
//             for (auto x : g[v]) if (!vis[x]) {
//                 dfs(dfs, x);
//             }
//         }};
//         bool ok{true};
//         for (int i{} ; i < (int)vis.size() ; i++) {
//             if (vis[i]) continue;
//             cnt = 0;
//             dfs(dfs, i);
//             if (cnt != 2) ok = false;
//         }
//         if (ok) ans = std::min(ans, n - (int)std::popcount((unsigned)bit));
//     }
//     return ans;
// }

int solve() {
    std::mt19937 mt{std::random_device{}()};
    int n;
    std::cin >> n;
    // n = mt() % 5 + 1;
    std::vector<std::pair<int, int>> RL(n);
    for (auto& [R, L] : RL) std::cin >> L >> R;
    // for (auto& [R, L] : RL) {
        // R = mt() % 20;
        // L = mt() % 20;
        // if (R < L) std::swap(L, R);
    // }
    std::vector g(n, std::vector<bool>(n));
    for (int i{} ; i < n ; i++) {
        for (int j{i + 1} ; j < n ; j++) {
            if (Intersect(RL[i], RL[j])) {
                g[i][j] = true;
            }
        }
    }
    using qt = std::tuple<int, int, int>;
    std::priority_queue<qt, std::vector<qt>, std::greater<qt>> que;
    for (int i{} ; i < n ; i++) {
        for (int j{i + 1} ; j < n ; j++) {
            if (g[i][j]) {
                que.emplace(std::max(RL[i].first, RL[j].first), i, j); 
            }
        }
    }
    std::vector<bool> del(n);
    int ans{n};
    while (que.size()) {
        auto [_, i, j]{que.top()};
        que.pop();
        if (del[i] or del[j]) continue;
        ans -= 2;
        for (int k{} ; k < n ; k++) {
            if (del[k]) continue;
            if (g[i][k] or g[k][i]) del[k] = true;
            if (g[j][k] or g[k][j]) del[k] = true;
        }
    }
    // if (ans != brute(RL)) {
    //     for (auto [R, L] : RL) std::cout << L << ' ' << R << std::endl;
    //     std::cout << "you " << ans << std::endl;
    //     std::cout << "tak " << brute(RL) << std::endl;
    //     exit(0);
    // }
    return ans;
}
    
int main() {
    SetFastIO();

    int t; std::cin >> t;
    while (t--) {
        std::cout << solve() << '\n';
        // std::cout << solve() << std::endl;
    }
}

感想

• 合計1h8m、バチャからロスタイム19分でのACとなった。酷すぎる。
• Cまでに1h13mかかったのもひどい。
• 「ペアの片方を現在残っている区間の中で右端が最小のものとしていよい」という予想が嘘であることを愚直を書いて照らし合わせるまで気づけなかった。
• 愚直も永遠バグらせた。本当にひどい。