成績上昇大作戦 [ICPC JAG 模擬国内予選 2019 E]

問題分と入出力

前提知識

• 最大クリーク

解説

M≦40なので、ビット的な計算量が出てくるだろうと仮定を立てる。
しかも、40というのは微妙な所で2^Mというのは間に合わない。
だが、2^(M/2)なら間に合う。
半分全列挙である。
ここで終わった。
　
最大クリークらしい。
なるほど。
a番目の科目とb番目の科目がどちらも広義単調増加にできれば、頂点aと頂点bに辺を貼る。
これでM頂点の無向グラフができる。
このグラフの最大クリークが答えになる。
　
どちらも広義単調増加にできるかという判定は、{A[i][a], A[i][b]}のペアでN日分配列に入れて、
昇順ソートをする。
これで、a番目の科目については広義単調増加になった。
この状態でb番目の科目が広義単調増加であれば、どちらも広義単調増加にできる。
　

int N, M, A[1010][40];
//---------------------------------------------------------------------------------------------------
void solve() {
	MaxClique mc;
	mc.init(M);

	rep(a, 0, M) rep(b, a + 1, M) {
		vector<pair<int, int>> v;
		rep(i, 0, N) v.push_back({ A[i][a] , A[i][b] });
		sort(all(v));

		bool ok = true;
		rep(i, 0, N - 1) if (v[i].second > v[i + 1].second) ok = false;
		if (ok) mc.addEdge(a, b);
	}

	int ans = mc.solve();
	cout << ans << endl;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	while (cin >> N >> M) {
		if (N == 0) return;
		rep(i, 0, N) rep(j, 0, M) cin >> A[i][j];
		solve();
	}
}