Codeforces 673B - Problems for Round

問題

codeforces.com

次のCodeforcesのラウンドでは問が出題されます。問題は昇順の難易度を持っています。
またこの中には類似した問題のペアが組存在しています。これらをdiv1とdiv2の問題セットに分けてください。その際以下のルールに従わなくてはなりません。

1. 各問題セットは空であってはならない。
2. 類似した問題は同じ問題セットに入れてはならない。
3. div2のどの問題よりもdiv1の問題の方が難しくなくてはならない。
4. 各問題はただ一度だけ使わなくてはならない。

このルールに従って問題を分割する方法は何通りあるでしょうか。

解法

組のペアが与えられるのでそれらのうち難易度が低い方がdiv2、高い方がdiv1に属することになります。この際、すでにdiv2に分配されていた問題をdiv1に分配しなくてはならない状況(div2とdiv1を読み替えたパターンも考える)や、div2のある問題の難易度がdiv1にある問題の難易度を超えてしまう状況が起こり得ます。このときは問題を分割する方法は0通りです。
何事もなく類似関係にある問題を分配できたのならば、あとは残りの問題を分配する方法を考えます。上で挙げた3つめの条件から自由に分配でき得るのは、を満たす問題だけであることがわかります。どこにdiv1とdiv2の境界線を置くかを考えると、そのような方法は通りとなります。
そしてもう一つコーナーケースがあります。の場合は先程同様どこに境界線を置くかを考えることにより、通りと求められます。

ソースコード

#include <iostream>
#include <set>
using namespace std;

#define REP(i, x) for (int i = 0; i < (x); i++)
#define ALL(a) (a).begin(), (a).end()

const int INF = 1000000;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    set<int> div1, div2;
    int n, m, mindiv1 = INF, maxdiv2 = -1;

    cin >> n >> m;

    bool ok = true;
    REP (i, m) {
        int u, v;
        cin >> u >> v;
        if (u > v) swap(u, v);
        if (div1.find(u) != div1.end()) ok = false;
        if (div2.find(v) != div2.end()) ok = false;

        div1.insert(v);
        div2.insert(u);
        mindiv1 = min(mindiv1, v);
        maxdiv2 = max(maxdiv2, u);
    }

    int ans = 0;
    if (m == 0) {
        ans = n - 1;
    } else if (ok && maxdiv2 < mindiv1) {
        ans = mindiv1 - maxdiv2;
    }

    cout << ans << endl;

    return 0;
}

感想

多分もう二度とこんな丁寧なエントリは書かないと思います。(*^_^*)