Atcoder Grand Contest 010 E. Rearranging

Atcoder Grand Contest 010 E. Rearranging

E: Rearranging - AtCoder Grand Contest 010 | AtCoder

感想

とにかく自力でACできて喜んでいたが、うさぎさんのコードを見ると圧倒的に簡潔でわかりやすかったので、大幅に真似て改良した。
AtCoder Grand Contest 010: E - Rearranging · うさぎ小屋

ちなみにこの問題は、以下の問題に近いものを感じた。こちらをACしていたから解けたのだと思う。
F: Wide Swap - AtCoder Grand Contest 001 | AtCoder

解法

まず先手がどのようにすれば最適な数列を構成できるかを考える。各数に関して、自分と互いに素ではない数に対して辺を張ることを考える。このとき連結にならないもの同士は、どう配置してもスワップできるので、独立に考えて最後に適当に（てきとーに）並べればよい。

ある連結成分について、最適な数列を構成する。まず、その成分の中で最小の値を一番左に置くのが最適である。なぜなら、その数を置いたときに任意の$\ DFS\ $順でそれ以降の数を並べていけば、その最初の数がスワップによって後ろの移動することはないからである。

さて、ある値を置いたあとに、その右に置く数はどんな数であるかを考える。その数と互いに素ではない数がまだ存在するなら、その数の中で最小のものを置けば良い。その数はその左の数とスワップされることはないし、もし仮に互いに素であるが、それよりも小さい数が存在したとしても、それを置いてしまうとスワップによってより大きくされてしまうはずであるからだ。

もし存在しないならば、まだ使っていない数の中で最小のものを置けば良い。ここで、より小さい数を選ぶことになる場合は明らかに問題がないのだが、より大き数数を選ぶ場合は最適でない可能性があるようにも思われる。しかし、そのような数というのはどのように配置してもスワップを防ぎきれないものであることがわかる。

以上の数列は$\ a\ $をソートしておき、常に左から順に見るような実装であれば、単純に$\ DFS\ $をするだけで求めることができる。

次に後手が作る最適な数列の構成法を考える。互いに素でない2つの数$\ a_i, a_j(i < j)\ $に関して、$\ a_j\ $から$\ a_i\ $に向かって有効辺を張ったときのトポロジカルソートの中で辞書順最大のものがその最適な数列である（AGC_001 Fとほとんど同じ）。

これは、出次数が$\ 0\ $のものの中で最大の数を一番左にもってきて、その数を消す、という操作を繰り返していくと求めることができる。上に書いたように辺を張ると、辺を削るときに困るので、逆向きに辺を張り、入次数が0のものとして考えると次数を減らす操作が簡単になる。

このようにやったものの、実は挿入ソートをやればよかった。なぜかこれに気づかなかった。実装の仕方はうさぎさんのを真似した。

実装（自力で書いた長くて汚い方）

#include "bits/stdc++.h"
using namespace std;
 
#define all(x)  x.begin(), x.end()
#define mp      make_pair
 
vector<int> g[2020];
int used[2020];
vector<int> a;
vector<int> tmp;
 
void dfs(int v, int prev) {
        used[v] = true;
        tmp.push_back(a[v]);
        vector<pair<int, int>> p;
        for (auto u : g[v]) if (u != prev) p.emplace_back(a[u], u); sort(all(p));
        for (auto u : p) {
                if (!used[u.second]) {
                        dfs(u.second, v);
                }
        }
}
 
int main() {
        int n;
        scanf("%d", &n);
        a.resize(n);
        for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
        sort(all(a));
        for (int i = 0; i < n; i ++) {
                for (int j = i + 1; j < n; j ++) {
                        if (__gcd(a[i], a[j]) != 1) {
                                g[i].push_back(j);
                                g[j].push_back(i);
                        }
                }
        }
        for (int i = 0; i < n; i ++) {
                if (!used[i]) {
                        dfs(i, -1);
                }
        }
        for (int i = 0; i < n; i ++) g[i].clear();
        for (int i = 0; i < n; i ++) {
                for (int j = i + 1; j < n; j ++) {
                        if (__gcd(tmp[i], tmp[j]) != 1) {
                                g[i].push_back(j);
                        }
                }
        }
        vector<int> in_cnt(n, 0);
        for (int i = 0; i < n; i ++) {
                for (auto u : g[i]) {
                        in_cnt[u] ++;
                }
        }
        priority_queue<pair<int, int>> pq;
        for (int i = 0; i < n; i ++) if (in_cnt[i] == 0) pq.push(mp(tmp[i], i));
        vector<int> ans;
        while (!pq.empty()) {
                auto get = pq.top();
                pq.pop();
                ans.push_back(get.first);
                for (auto u : g[get.second]) {
                        in_cnt[u] --;
                        if (in_cnt[u] == 0) pq.push(mp(tmp[u], u));
                }
        }
        for (int i = 0; i < n; i ++) cout << ans[i] << (i == n - 1 ? '\n' : ' ');
        return 0;
}

実装（うさぎさんのコードを真似て書いたコード）

#include "bits/stdc++.h"
using namespace std;

#define all(x)  x.begin(), x.end()

int n;
int used[2020];
vector<int> a, ans;

void dfs(int v) {
        used[v] = true;
        ans.push_back(a[v]);
        for (int u = 0; u < n; u ++) {
                if (!used[u] && __gcd(a[v], a[u]) != 1) dfs(u);
        }
}

int main() {
        scanf("%d", &n);
        a.resize(n);
        for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
        sort(all(a));
        for (int i = 0; i < n; i ++) if (!used[i]) dfs(i);
        for (int i = 0; i < n; i ++) {
                int p = i;
                for (int j = i - 1; j >= 0 && __gcd(ans[i], ans[j]) == 1; j --) {
                        if (ans[j] < ans[i]) p = j;
                }
                rotate(ans.begin() + p, ans.begin() + i, ans.begin() + i + 1);
        }
        for (int i = 0; i < n; i ++) cout << ans[i] << (i == n - 1 ? '\n' : ' ');
        return 0;
}