Yukicoder No.489 株に挑戦

,

https://yukicoder.me/problems/no/489

yukicoderではavxが使える。嘘解法力の上昇を感じる。

solution

愚直。$O(ND)$。

コンパイラさんがお仕事しやすいように、一度$\max \{ x_k \mid j \le k \le j + D \}$だけ単体で求めてから復元するように書くとよい。

implementation

pragma付けるだけでよろしくしてくれて驚き。 objdumpするとXMMWORDvpmaxsd命令が吐かれていることが確認できた。

#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")
#include <cstdio>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i))
using ll = long long;
using namespace std;
constexpr int MAX_N = 1e5;
int x[MAX_N];
int main() {
    int n, d, K; scanf("%d%d%d", &n, &d, &K);
    repeat (i,n) scanf("%d", &x[i]);
    int mx = 0, mj = -1;
    repeat (j,n) {
        int acc = 0;
        repeat_from (k,j,min(n,j+d+1)) acc = max(acc, x[k]); // simd
        if (mx < acc - x[j]) {
            mx = acc - x[j];
            mj = j;
        }
    }
    int mk = -1;
    repeat_from (k,mj,min(n,mj+d+1)) {
        if (mx == x[k] - x[mj]) {
            mk = k;
            break;
        }
    }
    printf("%lld\n", mx*(ll)K);
    if (mx) printf("%d %d\n", mj, mk);
    return 0;
}

Yukicoder No.488 四角関係

,

https://yukicoder.me/problems/no/488

golfしようと思ってそのままpythonで書いたやつを削ったら定数倍が重くなっててTLEした。

solution

全探索。$O(N^4)$。

重複して数えないこと、条件を満たす$4$つの頂点$(i,j,k,l)$は必ずしも$i \lt j \lt k \lt l$ではないことに注意する。

implementation

#!/usr/bin/env python3
n, m = map(int, input().split())
g = [ [ False for _ in range(n) ] for _ in range(n) ]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = g[b][a] = True
cnt = 0
for a in range(n):
    for b in range(a):
        for c in range(b):
            for d in range(c):
                for i, j, k, l in [ (a,b,c,d), (a,c,b,d), (a,c,d,b) ]:
                    if g[i][j] and g[j][k] and g[k][l] and g[l][i] and not g[i][k] and not g[j][l]:
                        cnt += 1
print(cnt)




Yukicoder No.484 収穫

,

https://yukicoder.me/problems/no/484

解けず。解けるべきだった。

solution

区間DP。端から使っていく。$O(N^2)$。

ある区間$[l,r)$がまだ全て使われておらずこの外は全て使われているとする。 このとき次に使うのは位置$l,r-1$のどちらか。 $l,r-1$より先に$l \lt m \lt r-1$な$m$を使ったとしても、その後$l,r-1$を両方使わなければいけないので結局そのために位置$m$を横切る。 つまり$m$は後回しでも問題ない。

implementation

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
const int inf = 1.01e9;
int main() {
    int n; cin >> n;
    vector<int> a(n); repeat (i,n) cin >> a[i];
    auto dp = vectors(2, n+1, n+1, inf);
    dp[false][1][n] = a[0];
    dp[true][0][n-1] = a[n-1];
    repeat_reverse (len,n+1) {
        repeat (l,n-len+1) {
            int r = l + len;
            if (0 <= l-1) {
                setmin(dp[false][l][r], max(dp[false][l-1][r]+1,     a[l-1]));
                setmin(dp[false][l][r], max(dp[true ][l-1][r]+r-l+1, a[l-1]));
            }
            if (r+1 < n+1) {
                setmin(dp[true][l][r], max(dp[false][l][r+1]+r-l+1, a[r]));
                setmin(dp[true][l][r], max(dp[true ][l][r+1]+1,     a[r]));
            }
        }
    }
    int ans = inf;
    repeat (p,2) repeat (l,n+1) setmin(ans, dp[p][l][l]);
    cout << ans << endl;
    return 0;
}

Codeforces Round #270: G. Design Tutorial: Increase the Constraints

,

http://codeforces.com/contest/472/problem/G

SIMDによる嘘解法。 codeforcesはAVXまでしか使えない、かつintrinsicは(ものにもよるだろうがAVXのだと)target specific option mismatchと言われてだめなので注意すること。気付かず書くとcompile errorや実行時にinvalid instructionする。両方踏んだ。

solution

愚直 + SIMD。$O(Q \cdot \mathrm{len})$。

一致比較には'0' = 48, '1' = 49により'0' ^ '1' = 1なのでpvxorを利用した。集計はvpaddbで垂直に足していって、(桁上がりが発生する前の適当なタイミングで)charとして水平に足し合わせた。

implementation

http://codeforces.com/contest/472/submission/24931343

#include <cstdio>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
#define LEN_MAX 200000
char a[LEN_MAX+1];
char b[LEN_MAX+1];
int main() {
    int q; scanf("%[01] %[01]%d", a, b, &q);
    for (char *p = a; *p; ++ p) *p = (*p == '1');
    for (char *p = b; *p; ++ p) *p = (*p == '1');
    while (q --) {
        int p1, p2, len; scanf("%d%d%d", &p1, &p2, &len);
        int cnt = 0;
        int i = 0;
        for (; i < len-16; ) {
            __asm__ (
                    "pxor %%xmm1, %%xmm1 ;" :);
            for (int j = 0; j < 127 and i < len-16; ++ j, i += 16) {
                volatile char *pa = a + p1 + i;
                volatile char *pb = b + p2 + i;
                __asm__ (
                        "vmovdqu (%0), %%xmm2 ;"
                        "vmovdqu (%1), %%xmm3 ;"
                        "vpxor %%xmm2, %%xmm3, %%xmm2 ;"
                        "vpaddb %%xmm1, %%xmm2, %%xmm1 ;"
                        : : "r" (pa), "r" (pb));
            }
            volatile char acc[16];
            __asm__ (
                    "vmovdqu %%xmm1, (%0) ;"
                    : : "r" (acc));
            repeat (k,16) cnt += acc[k];
        }
        for (; i < len; ++ i) if (a[p1 + i] != b[p2 + i]) ++ cnt;
        printf("%d\n", cnt);
    }
    return 0;
}

AtCoder Regular Contest 028: D - 注文の多い高橋商店

,

http://arc028.contest.atcoder.jp/tasks/arc028_4

$10^9$はloopの中身が十分軽くないと厳しいと認識してたが、やればACに持っていける量という認識に改めるべきかも。

solution

簡単に前処理 + 定数倍を頑張る。$O(M(N + Q))$。

区間$[0,k)$で$l$個使う方法の数$\mathrm{dp}_L(k,l)$と区間$(k,N)$で$r$個使う方法の数$\mathrm{dp}_R(k,r)$をそれぞれ$O(NM)$で前もって求めておく。 するとクエリ$(k,x)$について答え$\mathrm{ans} = \sum_l \mathrm{dp}_L(k,l) \cdot \mathrm{dp}_R(k,M-l-x)$であり、クエリあたり$O(M)$となる。

定数倍最適化に関して、以下をすれば通った。

  • loop unrolling
  • prefetchが効くようreverse
  • (コンパイラがやってくれてなかったので) 一時変数へのくくり出し

implementation

http://arc028.contest.atcoder.jp/submissions/1128915

#include <cstdio>
#include <algorithm>
#define repeat(i,n) for (int i = 0; i < (n); ++i)
#define repeat_from(i,m,n) for (int i = (m); i < (n); ++i)
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
typedef long long ll;
using namespace std;
#define MAX_N 2000
#define MAX_M 2000
const int mod = 1000000007;
int a[MAX_N];
int dpl[MAX_N+1][MAX_M+1];
int dpr[MAX_N+1][MAX_M+1];
ll dpacc[MAX_M+2];
int main() {
    // input
    int n, m, q; scanf("%d%d%d", &n, &m, &q);
    repeat (i,n) scanf("%d", &a[i]);
    // prepare
    //     left
    dpl[0][0] = 1;
    repeat_from (i,1,n+1) {
        dpacc[0] = 0;
        repeat (j,m+1) dpacc[j+1] = dpacc[j] + dpl[i-1][j];
        repeat (j,m+1) dpl[i][j] = (dpacc[j+1] - dpacc[max(0, j-a[i-1])]) % mod;
    }
    //     right
    dpr[n][0] = 1;
    repeat_reverse (i,n) {
        dpacc[0] = 0;
        repeat (j,m+1) dpacc[j+1] = dpacc[j] + dpr[i+1][j];
        repeat (j,m+1) dpr[i][j] = (dpacc[j+1] - dpacc[max(0, j-a[i])]) % mod;
    }
    repeat (i,n+1) {
        reverse(dpr[i], dpr[i]+MAX_M+1);
    }
    // query
    repeat (query,q) {
        int k, x; scanf("%d%d", &k, &x); -- k;
        ll acc = 0;
        int *l = dpl[k];
        int *r = dpr[k+1] + MAX_M-m+x; // binding is required for optimization
        int j = 0;
        for (; j < m+1-x - 16; j += 16) {
            acc += l[j+ 0] *(ll) r[j+ 0] % mod;
            acc += l[j+ 1] *(ll) r[j+ 1] % mod;
            acc += l[j+ 2] *(ll) r[j+ 2] % mod;
            acc += l[j+ 3] *(ll) r[j+ 3] % mod;
            acc += l[j+ 4] *(ll) r[j+ 4] % mod;
            acc += l[j+ 5] *(ll) r[j+ 5] % mod;
            acc += l[j+ 6] *(ll) r[j+ 6] % mod;
            acc += l[j+ 7] *(ll) r[j+ 7] % mod;
            acc += l[j+ 8] *(ll) r[j+ 8] % mod;
            acc += l[j+ 9] *(ll) r[j+ 9] % mod;
            acc += l[j+10] *(ll) r[j+10] % mod;
            acc += l[j+11] *(ll) r[j+11] % mod;
            acc += l[j+12] *(ll) r[j+12] % mod;
            acc += l[j+13] *(ll) r[j+13] % mod;
            acc += l[j+14] *(ll) r[j+14] % mod;
            acc += l[j+15] *(ll) r[j+15] % mod;
        }
        for (; j < m+1-x; ++ j) {
            acc += l[j] *(ll) r[j] % mod;
        }
        printf("%lld\n", acc % mod);
    }
    return 0;
}

code festival 2014 上海: J - XORAND

,

http://code-festival-2014-china.contest.atcoder.jp/tasks/code_festival_china_j

SIMDの練習問題にと思ったのに、SIMDを書き始める前に通ってしまった。 clangさんは賢すぎるので何も言わずともvector化されてしまってるようだ。 2014年の問題なので当時は違ったのだろう。

problem

最初に列$A$が与えられる。クエリ$[l-1,r)$が与えられるのでそれぞれについて、$m = \max \{ {\bigwedge\mkern-15mu\bigwedge}_{l-1 \le i \lt m} A_i - \bigoplus_{m \le i \lt r} A_i \mid l-1 \lt m \lt r-1 \}$を答えよ。 ただしクエリの先読みはできないものとする。

solution

愚直っぽくやる。$O(NQ)$。

xorについては累積和を取っておいて適当に。 andについては高々$31$回しか変化しないので、bitごとに次の変化する位置のtableを持っておいて飛ぶようにする。

implementation

#include <cstdio>
#include <cstdint>
#include <cstdlib>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
typedef long long ll;
using namespace std;
const ll inf = ll(1e18)+9;
#define N_MAX 100000
int32_t a[N_MAX];
int32_t xor_acc[N_MAX+1];
int and_skip[N_MAX][31];
int main() {
    // input
    int n, q; scanf("%d%d", &n, &q);
    repeat (i,n) scanf("%u", &a[i]);
    // prepare
    xor_acc[0] = 0;
    repeat (i,n) xor_acc[i+1] = xor_acc[i] ^ a[i];
    repeat (k,31) and_skip[n-1][k] = n;
    repeat_reverse (i,n-1) {
        repeat (k,31) {
            and_skip[i][k] = and_skip[i+1][k];
            if (not (a[i+1] & (1<<k))) and_skip[i][k] = i+1;
        }
    }
    // query
    ll m = - inf;
    while (q --) {
        // input
        int l, r; scanf("%d%d", &l, &r);
        if (m == - inf) {
            -- l;
        } else {
            l = (l + abs(m)) % n;
            r = (r + abs(m)) % n + 1;
        }
        // solve
        m = - inf;
        int32_t d = a[l];
        for (int i = l; i < r-1; ) {
            int ni = r-1;
            repeat (k,31) if (d & (1<<k)) ni = min(ni, and_skip[i][k]);
            int32_t x = 0x7fffffff;
            repeat_from (j,i,ni) {
                x = min(x, xor_acc[r] ^ xor_acc[j+1]);
            }
            m = max(m, d -(ll) x);
            d &= a[ni];
            i = ni;
        }
        // output
        printf("%lld\n", m);
    }
    return 0;
}

Code Formula 2014 本選: H - 平和協定

,

http://code-formula-2014-final.contest.atcoder.jp/tasks/code_formula_2014_final_h

この大会は予選通ったがこの本戦は交通費支給が渋かったので蹴った記憶がある。 そしてそういう人が多かったのか次の年から開催が消えてしまった。

solution

loop unrollingする。$O(N^2)$。

implementation

多めに空間をとって踏んでも結果に影響しない値で埋めておくと楽。clangで提出しないと(たとえ#pragma GCC ...しても)TLEる。

#include <cstdio>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;
#define MAX_N 50000
const int inf = 1e9+7;
int a[MAX_N + 10];
int b[MAX_N + 10];
int main() {
    repeat (x, MAX_N + 10) a[x] = b[x] = inf;
    int n, s1, s2; scanf("%d%d%d", &n, &s1, &s2);
    repeat (i,n) scanf("%d%d", &a[i], &b[i]);
    int cnt = 0;
    repeat (x,n) {
        for (int y = x+1; y < n; y += 8) {
            ll d0 = (a[x] - a[y  ]) *(ll) (b[x] - b[y  ]);
            ll d1 = (a[x] - a[y+1]) *(ll) (b[x] - b[y+1]);
            ll d2 = (a[x] - a[y+2]) *(ll) (b[x] - b[y+2]);
            ll d3 = (a[x] - a[y+3]) *(ll) (b[x] - b[y+3]);
            ll d4 = (a[x] - a[y+4]) *(ll) (b[x] - b[y+4]);
            ll d5 = (a[x] - a[y+5]) *(ll) (b[x] - b[y+5]);
            ll d6 = (a[x] - a[y+6]) *(ll) (b[x] - b[y+6]);
            ll d7 = (a[x] - a[y+7]) *(ll) (b[x] - b[y+7]);
            if (s1 <= d0 and d0 <= s2) ++ cnt;
            if (s1 <= d1 and d1 <= s2) ++ cnt;
            if (s1 <= d2 and d2 <= s2) ++ cnt;
            if (s1 <= d3 and d3 <= s2) ++ cnt;
            if (s1 <= d4 and d4 <= s2) ++ cnt;
            if (s1 <= d5 and d5 <= s2) ++ cnt;
            if (s1 <= d6 and d6 <= s2) ++ cnt;
            if (s1 <= d7 and d7 <= s2) ++ cnt;
        }
    }
    printf("%d\n", cnt);
    return 0;
}

HackerRank University CodeSprint 2: Sherlock's Array Merging Algorithm

,

https://www.hackerrank.com/contests/university-codesprint-2/challenges/sherlocks-array-merging-algorithm

problem

$1, 2, \dots, n$の順列$M$が与えられる。問題文中の疑似言語で指示されたアルゴリズムで処理したとき、結果がこの$M$になるような入力$V$の種類数を答えよ。

solution

DP。$O(N^3)$。

ただし簡単な定数倍高速化が必要だった。

implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
using ll = long long;
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
const int mod = 1e9+7;
ll powmod(ll x, ll y, ll p) { // O(log y)
    assert (y >= 0);
    x %= p; if (x < 0) x += p;
    ll z = 1;
    for (ll i = 1; i <= y; i <<= 1) {
        if (y & i) z = z * x % p;
        x = x * x % p;
    }
    return z;
}
ll inv(ll x, ll p) { // p must be a prime, O(log p)
    assert ((x % p + p) % p != 0);
    return powmod(x, p-2, p);
}
int fact(int n) {
    static vector<int> memo(1,1);
    if (memo.size() <= n) {
        int l = memo.size();
        memo.resize(n+1);
        repeat_from (i,l,n+1) memo[i] = memo[i-1] *(ll) i % mod;
    }
    return memo[n];
}
int permute(int n, int r) {
    if (n < r) return 0;
    return fact(n) *(ll) inv(fact(n-r), mod) % mod;
}
const int N_MAX = 1200;
int permute_table_rev[N_MAX+1][N_MAX+1]; // important for optimization
int main() {
    repeat (i,N_MAX+1) repeat (j,N_MAX+1) permute_table_rev[j][i] = permute(i, j);
    int n; cin >> n;
    vector<int> m(n); repeat (i,n) cin >> m[i];
    vector<vector<int> > dp = vectors(n+1, n+1, int());
    dp[0][n] = 1;
    repeat (r,n+1) {
        repeat_reverse (l,r) {
            if (l+1 < r and m[l] > m[l+1]) break;
            ll acc = 0;
            repeat_from (k,r-l,n+1) {
                acc += dp[l][k] *(ll) (l == 0 ? 1 : permute_table_rev[r-l][k]) % mod;
            }
            dp[r][r-l] = acc % mod;
        }
    }
    ll ans = 0;
    repeat (j,n+1) ans += dp[n][j];
    cout << ans % mod << endl;
    return 0;
}

HackerRank University CodeSprint 2: The Story of a Tree

,

https://www.hackerrank.com/contests/university-codesprint-2/challenges/the-story-of-a-tree

problem

木、その隣接する頂点の順序対の列$(u_1, v_1), \dots, (u_g, v_g)$$、整数$k$が与えられる。 木の頂点を等確率でひとつ選んで根とするとき、$parent(v_i) = u_i$となるような$i$の数が$k$以上になる確率を答えよ。

solution

木の上でのimos法。$O(N + G)$ for each query。

implementation

#include <iostream>
#include <vector>
#include <functional>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
int gcd(int a, int b) { while (a) { b %= a; swap(a, b); } return b; }
int main() {
    int query; cin >> query;
    while (query --) {
        int n; cin >> n;
        vector<vector<int> > g(n);
        repeat (i,n-1) {
            int u, v; cin >> u >> v; -- u; -- v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        const int root = 0;
        vector<int> parent(n, -1); {
            function<void (int)> go = [&](int i) {
                for (int j : g[i]) if (j != parent[i]) {
                    parent[j] = i;
                    go(j);
                }
            };
            go(root);
        }
        int guess, k; cin >> guess >> k;
        vector<int> imos(n);
        while (guess --) {
            int u, v; cin >> u >> v; -- u; -- v;
            if (parent[v] == u) { // Alice's guess is true when root is 0
                imos[root] += 1;
                imos[v] -= 1;
            } else if (parent[u] == v) {
                imos[u] += 1;
            } else {
                assert (false);
            }
        }
        int cnt = 0;
        function<void (int, int)> go = [&](int i, int acc) {
            acc += imos[i];
            if (acc >= k) ++ cnt;
            for (int j : g[i]) if (j != parent[i]) go(j, acc);
        };
        go(root, 0);
        int d = gcd(cnt, n);
        cout << cnt/d << "/" << n/d << endl;
    }
    return 0;
}

HackerRank University CodeSprint 2: Game of Two Stacks

,

https://www.hackerrank.com/contests/university-codesprint-2/challenges/game-of-two-stacks

solution

自然数のstackがふたつと整数$x$が与えられる。 取り出した数の合計が$x$以上になるまで、ふたつのstackから好きに数を取り出してよい。 取り出す数の個数を最大化したとき、それはいくつか。

solution

しゃくとり法。$O(N + M)$ for each game。

implementation

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;
template <class T> void setmax(T & a, T const & b) { if (a < b) a = b; }
int main() {
    int games; cin >> games;
    while (games --) {
        int na, nb, x; cin >> na >> nb >> x;
        vector<int> a(na); repeat (i,na) cin >> a[i];
        vector<int> b(nb); repeat (j,nb) cin >> b[j];
        int result = 0;
        int i = 0;
        ll acc = 0;
        while (i < na and acc + a[i] <= x) {
            acc += a[i];
            ++ i;
        }
        int j = 0;
        while (true) {
            while (j < nb and acc + b[j] <= x) {
                acc += b[j];
                ++ j;
            }
            setmax(result, i + j);
            if (i == 0) {
                break;
            } else {
                -- i;
                acc -= a[i];
            }
        }
        cout << result << endl;
    }
    return 0;
}

HackerRank University CodeSprint 2: Separate the Numbers

,

https://www.hackerrank.com/contests/university-codesprint-2/challenges/separate-the-numbers

problem

与えられた文字列が公差$1$の正整数の等差数列(eg. $(9, 10, 11, 12)$)の$10$進表現を文字列結合(eg. 9101112)したものになっているか判定しその初項を答えよ。

implementation

先に答えを作って文字列比較すると楽。

#!/usr/bin/env python3
def solve(s):
    if s.startswith('0'):
        return
    n = len(s)
    for l in range(1, n-1):
        x = int(s[: l])
        t = ''
        y = x
        while len(t) < len(s):
            t += str(y)
            y += 1
        if t == s:
            return x
for _ in range(int(input())):
    s = input()
    x = solve(s)
    if x is not None:
        print('YES', x)
    else:
        print('NO')

HackerRank University CodeSprint 2: Breaking the Records

,

https://www.hackerrank.com/contests/university-codesprint-2/challenges/breaking-best-and-worst-records

problem

ある人がゲームで取った得点の列が与えられる。最高得点、最低得点の更新回数をそれぞれ答えよ。

solution

#!/usr/bin/env python3
n = int(input())
best, worst = float('-inf'), float('inf')
increased, decreased = -1, -1
for a in map(int, input().split()):
    if best < a:
        best = a
        increased += 1
    if worst > a:
        worst = a
        decreased += 1
print(increased, decreased)

AtCoder Grand Contest 010: E - Rearranging

,

http://agc010.contest.atcoder.jp/tasks/agc010_e

適当にやればできるという感じがあったので流れで書いたらなんとなく通った。ただしそのような書き方の常として、不注意なバグを埋めて苦しんだ。

solution

連結成分ごとに順序を立てて、仕上げに挿入ソート。$O(N^2)$。

互いに素でない数同士を辺で結んでグラフを作る。これは非連結であり、制約の範囲は各連結成分内で閉じている。 連結成分内で最も端に持ってきたい数を決めて、それからのDFSの訪問順に並べれば上手くいく。 DFSでなくBFSとかだとだめで、反例としては2 6 30 10みたいな合流するもの。

後攻の行うのはただの整列なのでそのようにやる。挿入ソートがよい。ただし貪欲に見るだけだと不足することに注意。

implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
int gcd(int a, int b) { while (a) { b %= a; swap(a, b); } return b; }
bool is_swappable(int a, int b) { return gcd(a, b) == 1; }
int main() {
    // input
    int n; cin >> n;
    vector<int> a(n); repeat (i,n) cin >> a[i];
    // rearrange
    whole(sort, a);
    vector<int> b;
    vector<bool> used(n);
    function<void (int)> go = [&](int i) {
        used[i] = true;
        b.push_back(a[i]);
        repeat (j,n) if (not used[j] and not is_swappable(a[i], a[j])) {
            go(j);
        }
    };
    repeat (i,n) if (not used[i]) {
        go(i);
    }
    // insertion sort
    repeat (i,n) {
        int j = i;
        for (int k = i-1; k >= 0 and is_swappable(b[k], b[i]); -- k) {
            if (b[k] < b[i]) j = k;
        }
        rotate(b.begin() + j, b.begin() + i, b.begin() + i + 1);
    }
    // output
    for (auto it : b) cout << it << ' '; cout << endl;
    return 0;
}