PCK 2017 本選 5: 朝昼晩ごはん

この難易度帯にしては難しいなあと思ったら、自分の解法が想定と違った。

問題概要

日本語なので原文参照 → Aizu Online Judge

解説

人 と人 の食事の時間を同時に満たせるかどうかを考える。この判定は if 文で容易に行える。

さて、元の問題は「 に含まれる任意の人の組 について、食事の時間を同時に満たせるような人の部分集合 のうち、集合の濃度 (サイズ) が最大のもの」を求める問題であるが、 と が食事の時間を同時に満たせるときに 間に無向辺を張るものとすると、 に含まれる頂点は完全グラフを成す、すなわちクリークである。今回はサイズが最大のものを答えるので、つまりは最大クリーク問題である。

グラフ における最大クリーク問題は、 の補グラフ (隣接関係を逆転させたグラフ) において最大独立集合と等価である。枝狩りすると今回の制約でも高速に解けるため、AC できる。

ソースコード

// 最大独立集合問題ライブラリ 省略
int main() {
    int N; cin >> N;

    vector<int> ast(N), aet(N), hst(N), het(N), bst(N), bet(N);
    for(int i=0; i<N; i++) {
        for(int j=0; j<6; j++) {
            int h, m; cin >> h >> m;
            int t = h * 60 + m;
            if(j == 0) ast[i] = t;
            if(j == 1) aet[i] = t;
            if(j == 2) hst[i] = t;
            if(j == 3) het[i] = t;
            if(j == 4) bst[i] = t;
            if(j == 5) bet[i] = t;
        }
    }

    Graph<int> G(N);
    for(int i=0; i<N; i++) {
        for(int j=i+1; j<N; j++) {
            bool isc = true;
            if(aet[i] < ast[j]) isc = false;
            if(aet[j] < ast[i]) isc = false;
            if(bet[i] < bst[j]) isc = false;
            if(bet[j] < bst[i]) isc = false;
            if(het[i] < hst[j]) isc = false;
            if(het[j] < hst[i]) isc = false;

            if(!isc) {
                G[i].emplace_back(j);
                G[j].emplace_back(i);
            }
        }
    }

    MaximalIndependentSet<> mis(G);
    cout << mis.solve() << endl;
}