CS Academy Divisor Clique

リンク : https://csacademy.com/contest/archive/task/divisor_clique/statement/

問題概要

長さNの数列が与えられ、いくつか選んで数列を作る。この数列から任意の二数A、B(A>B)をとってきたら、必ず A%B=0 となる数列の最大の長さを答えよ。

解法

dp[i][j] : i番目までにj個とるまでの最小の最後の値とか考えていたら、例3でやられてしまった。今回大切なのは個数であり、最後の値の最小化ではないため、考えがずれていたことに気が付いた。そこで、ソートしておくと、次にとることのできる数字を簡単に(O(N^2))列挙することができ、最後の値を気にせずに済む。今回の場合はdpというよりもDAGとして見たほうが実装が楽になる。

またソートしておいたことによって前から見ていくとトポロジカル順序になっており、最長経路を求める問題となる。

LL N,A[2100],dp[2100];
vector<vector<LL>>g;
int main() {
	cin >> N;
	g.resize(N+1);
	rep(i, N) {
		cin >> A[i];
	}
	A[N] = 1;
	N++;
	sort(A, A + N);
	rep(i, N) {
		for(int j=i+1;j<N;j++) {
			if (A[j] % A[i] == 0) {
				g[i].push_back(j);
			}
		}
	}
	rep(i, N) {
		rep(j, g[i].size()) {
			dp[g[i][j]] = max(dp[g[i][j]], dp[i] + 1);
		}
		ans = max(ans, dp[i]);
	}
	cout << ans << endl;
	return 0;
}