hogecoder

tsutaj 競技プログラミングの記録

KUPC2012 D: 権力

何でこれが詰まっちゃうかな・・・。

問題概要

原文 → D: 権力 - 京都大学プログラミングコンテスト2012 | AtCoder

 M 個の区間がある。 \left[1, N \right] を被覆するには、区間はいくつ必要であるか、その最小値を答えよ。

解説

まず、地点  1 を被覆する区間があるかを調べます。もし存在するならば、その中で一番右まで被覆できるものを選びます。存在しなければ Impossible です。

次に、先ほど選んだ区間の右端  + 1 の地点を被覆する区間があるかを調べ、存在するならば一番右まで被覆できるものを選びます。

これを繰り返す貪欲法によって正答が得られ、計算量は  O(NM) です。

ソースコード

signed main() {
    int n, m; cin >> n >> m;
    int a[110], b[110];
    rep(i,0,m) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
    }
    bool covered[110] = {};
    int ans = 0;
    rep(i,0,n) {
        if(covered[i]) continue;
        int r = -1;
        rep(j,0,m) {
            if(a[j] <= i && i <= b[j]) {
                r = max(r, b[j]);
            }
        }
        if(r == -1) {
            cout << "Impossible" << endl;
            return 0;
        }
        repq(j,i,r) covered[j] = true;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

どうも区間の問題が苦手らしい。