AGC010E: Rearranging

https://beta.atcoder.jp/contests/agc010/tasks/agc010_e

O(N^4)からの高速化が思いつかなかった…。

まずAiを頂点としたグラフを考えて、互いに素ではない頂点同士をつなげます。すると各連結成分で一番小さい要素をcとしてcのうち最大のものを取るのが最適だとわかります。cをとった連結成分で次に取る要素はcと連結しているものです。

これでO(N^4)になったので高速化します。

ある頂点と連結している要素で一番小さいものを取っていく操作を繰り返します。そうすることで出来たDFS木について考えましょう。
ある頂点vの子piについて最適な数列Spiが求まっているとすると、vの最適な数列Sは先頭がvで、あとはSpiの先頭の要素のうち最大のものをpvとしてApvをSに追加し、pvはSpiから削除することを繰り返すことによって得られます。

これで主要なパートはO(N^2)でできるので間に合います。

なにかを順序を決めて取っていく問題でDFSとトポロジカル順はとても重要ですね。
無向グラフは少し使えるようになってきたと思うけど、有向グラフもすぐに書けるようになりたいですね。

int N;
int A[MAX_N];
bool used[MAX_N];
vector<int> G[MAX_N];

vi loop(int v) {
	used[v] = true;
	vector<vi> E;
	vector<int> at, res, order;

	if(v != 0) res.pb(A[v]);

	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(used[n]) continue;
		order.pb(i);
	}
	sort(all(order), [&](int a, int b){ return A[G[v][a]] < A[G[v][b]]; });

	rep(i, 0, sz(order)) {
		int n = G[v][order[i]];
		if(!used[n]) {
			E.pb(loop(n));
			at.pb(0);
		}
	}

	int m = sz(E);
	while(true) {
		int a = -1, tat = -1;
		rep(i, 0, m) {
			if(sz(E[i]) == at[i]) continue;
			if(a < E[i][at[i]]) {
				a = E[i][at[i]]; tat = i;
			}
		}
		if(tat == -1) break;
		at[tat]++; res.pb(a);
	}
	return res;
}

void solve() {
	cin >> N;
	rep(i, 0, N) {
		cin >> A[i + 1];
	}
	rep(i, 1, N + 1) {
		rep(j, i + 1, N + 1) {
			if(gcd(A[i], A[j]) != 1) {
				G[i].pb(j);
				G[j].pb(i);
			}
		}
	}
	rep(i, 1, N + 1) {
		G[i].pb(0);
		G[0].pb(i);
	}

	vector<int> ans = loop(0);
	rep(i, 0, N) {
		cout << ans[i] << " ";
	}
	cout << "\n";
}

Editorialが簡潔ですごい。