APIO2009 "The Siruseri Convention Centre"解いた

概要

番号つきの区間の集合が与えられ、被らない最大個数の区間集合を求める。ただし最大個数の区間集合が複数通りある場合、辞書順で小さいものを選ぶ。

手法

被らない最大個数の区間集合を求める問題は、簡単なDP(区間をendで整列し、ranges[upper_bound(ranges[x].begin)-1].rank+1とranges[x-1].rankのうち大きいほうをとる)という方法で列挙できる。このDPにおける計算の依存関係をグラフに起こすことで、最大値を与える列をグラフから生成できるようになる。

このグラフは次のようなものである。

• 全ての頂点は最大2つの後方リンクをもつ。自身のendの直前(自身を使わなかった場合のリンク)と、自身のbeginの直前(自身を使った場合のリンク)である。前者をサブリンク、後者をメインリンクと呼ぶことにする。
• 後方リンクもしくは前方リンクが無くなった時点でその頂点もろとも消滅する。
• 左側には番兵-1がおかれ、複数の頂点からリンクされる。右側は番兵nがn-1をリンクするのみである。
• その頂点が使用されるとは、グラフの経路上においてその頂点のメインリンクが使用されることと対応する。
• 使用可能な頂点のランクを「左から何番目の区間として出力されるか」と定めると、このランクはこの時点で全ての頂点で一意に決まる。サブリンクは同一ランク内でのリンクであり、メインリンクは下位ランクへのリンクである。

これらの中から最小辞書順を与えるものを取りだしたい。そのため以下のようなアルゴリズムを考える。

• 番号がxの区間が使用可能か調べる。(xのメインリンクが使用可能か調べる。)
  • 使用可能なら、番号xの区間を使用することにする。(xと同一ランクの他の頂点のメインリンクを削除する。)
• x = x + 1

この結果、最初辞書順のものが求まる。

コード

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

struct entry {
    int begin;
    int end;
    int id;
    int rank;
    bool usable;
    set<int> backlinks;
    set<int> forwardlinks;
    int mainlink;
    entry() : rank(0), usable(false) {}
    entry(int temp_end) : end(temp_end) {}
    bool operator<(const entry& o) const {
        return end < o.end;
    }
};
void search0(vector<entry>& ranges, int i) {
    if(ranges[i].usable)return;
    ranges[i].usable=true;
    for(set<int>::iterator j = ranges[i].backlinks.begin(); j != ranges[i].backlinks.end(); j++) {
        if(*j >= 0) {
            ranges[*j].forwardlinks.insert(i);
            search0(ranges, *j);
        }
    }
}
void disable(vector<entry>& ranges, int i) {
    if(i<0 || i>=(int)ranges.size() || !ranges[i].usable)return;
    if(ranges[i].forwardlinks.empty() || ranges[i].backlinks.empty()) {
        ranges[i].usable = false;
        for(set<int>::iterator j = ranges[i].backlinks.begin(); j != ranges[i].backlinks.end(); j++) {
            if(*j >= 0) {
                ranges[*j].forwardlinks.erase(i);
                disable(ranges, *j);
            }
        }
        for(set<int>::iterator j = ranges[i].forwardlinks.begin(); j != ranges[i].forwardlinks.end(); j++) {
            if(*j < (int)ranges.size()) {
                ranges[*j].backlinks.erase(i);
                disable(ranges, *j);
            }
        }
    }
}

int main(int argc, char **argv)
{
    int n;
    scanf("%d", &n);

    vector<entry> ranges(n);
    for(int i = 0; i < n; i++) {
        scanf("%d%d", &ranges[i].begin, &ranges[i].end);
        ranges[i].end++;
        ranges[i].id = i;
    }
    sort(ranges.begin(), ranges.end());
    vector<int> id_map(n);
    vector<int> rank_map(n+1);
    for(int i = 0; i < n; i++) {
        id_map[ranges[i].id] = i;
    }
    for(int i = 0; i < n; i++) {
        int backlink0 = upper_bound(ranges.begin(), ranges.begin()+i, entry(ranges[i].begin))-ranges.begin()-1;
        int backlink0_rank = backlink0>=0 ? ranges[backlink0].rank+1 : 0;
        int backlink1 = i-1;
        int backlink1_rank = backlink1>=0 ? ranges[backlink1].rank : -1;
        ranges[i].rank = max(backlink0_rank, backlink1_rank);
        ranges[i].mainlink = -1;
        if(ranges[i].rank == backlink0_rank) {
            ranges[i].backlinks.insert(backlink0);
            ranges[i].mainlink = backlink0;
        }
        if(ranges[i].rank == backlink1_rank) {
            ranges[i].backlinks.insert(backlink1);
        }
        rank_map[ranges[i].rank+1] = i+1;
    }
    ranges[n-1].forwardlinks.insert(n);
    search0(ranges, n-1);
    printf("%d\n", ranges[n-1].rank+1);
    for(int iid = 0; iid < n; iid++) {
        int i = id_map[iid];
        if(ranges[i].usable && (ranges[i].mainlink == -1 || ranges[ranges[i].mainlink].usable)
                && ranges[i].backlinks.find(ranges[i].mainlink)!=ranges[i].backlinks.end()) {
            //printf("%d(%d)\n", i, iid);
            printf("%d ", iid+1);
            for(int j = rank_map[ranges[i].rank]; j < rank_map[ranges[i].rank+1]; j++) {
                if(j==i)continue;
                ranges[j].backlinks.erase(ranges[j].mainlink);
                if(ranges[j].mainlink>=0) {
                    ranges[ranges[j].mainlink].forwardlinks.erase(j);
                }
                disable(ranges, j);
                disable(ranges, ranges[j].mainlink);
            }
        }
    }
    printf("\n");fflush(stdout);
    return 0;
}