この難易度帯にしては難しいなあと思ったら、自分の解法が想定と違った。
問題概要
日本語なので原文参照 → 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; }