Codeforces Global Round 15 C. Maximize the Intersections (R1800)

企業合コンで解いた。ギャグ系だった。

• 問題へのリンク

問題概要

円周上に 個の点があって、2 個ずつ 組のペアを作って線分で結ぶ。

すでに 組のペアができていて、線分が結ばれている。残りの点についてペアを作って線分を作っていったときの交差数の個数の最大値を求めよ。

制約

• 
• テストケース数

考えたこと

最初ヤバそうな問題に思えた。

線が結ばれずに残っている点について、番号が小さい方と大きい方に分けて、小さい方の 番目と大きい方の 番目を結ぶようにすればよい。

コード

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int N, K;
    cin >> N >> K;
    vector<int> aite(N*2, -1);
    set<int> edges;
    for (int i = 0; i < K; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        if (a > b) swap(a, b);
        aite[a] = b;
        edges.insert(a), edges.insert(b);
    }
    vector<int> non;
    for (int i = 0; i < N*2; ++i) if (!edges.count(i)) non.push_back(i);
    for (int i = 0; i < non.size()/2; ++i) aite[non[i]] = non[i+non.size()/2];
    
    int res = 0;
    for (int i = 0; i < aite.size(); ++i) {
        for (int j = i+1; j < aite.size(); ++j) {
            if (aite[i] == -1 || aite[j] == -1) continue;
            if (aite[i] < aite[j] && j < aite[i]) ++res;
        }
    }
    cout << res << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) solve();
}