Atcoder Grand Contest 008 D. K-th K
Atcoder Grand Contest 008 D. K-th K
D: K-th K - AtCoder Grand Contest 008 | AtCoder
解法
位置が確定しているものを左から順に確定させ、その数の左側に置かなければいけない個数を空いている場所に左詰めで書いていく。これができない場合は不可能。
位置が確定しているものをすべて書くことができたら、次にそれらの数の右側に置かなければいけない個数を左詰めで書いていく。これができない場合も不可能。
これらはどこまで書き込んだを示すポインタを一つ持つことで実装できる。$\ O(n^2)\ $。
#include "bits/stdc++.h" using namespace std; #define all(x) x.begin(), x.end() int main() { int n; scanf("%d", &n); vector<pair<int, int>> x(n); for (int i = 0; i < n; i ++) { scanf("%d", &x[i].first); x[i].first --; x[i].second = i + 1; } sort(all(x)); int sp = 0; vector<int> ans(n * n, -1); for (int i = 0; i < n; i ++) { ans[x[i].first] = x[i].second; int add = x[i].second - 1; while (add --) { if (ans[sp] != -1) add ++; else ans[sp] = x[i].second; sp ++; if (sp > x[i].first) return !puts("No"); } } for (int i = 0; i < n; i ++) { if (ans[sp] == -1 && sp < x[i].first) return !puts("No"); int add = n - x[i].second; while (add --) { if (ans[sp] != -1) add ++; else ans[sp] = x[i].second; sp ++; } } puts("Yes"); for (int i = 0; i < n * n; i ++) cout << ans[i] << (i == n * n - 1 ? '\n' : ' '); return 0; }
Atcoder Grand Contest 013 E. Placing Squares(追記）
Atcoder Grand Contest 013 E. Placing Squares(追記)
E: Placing Squares - AtCoder Grand Contest 013 | AtCoder
感想
愚直$\ DP\ $の高速化に失敗したので、解説放送を見て想定解を実装した。
解法
$\ 0\ $から$\ n\ $までの任意の位置に柵をおいて、その柵で囲まれたところそれぞれに2色のボールを置く（同じ位置でも良い）ときの場合の数を求めればそれが答えである。
解説放送ではこれに気づけばあとは自明な$\ DP\ $で解けると言っていたが、この遷移で少し悩んだので丁寧に書く。
まず$\ dp[i][j] := \ $（区間$\ [0, i)\ $の配置が完了していて、完了している区間の中で一番右の柵より右側に置いてあるボールの個数が$\ j\ $個となっている場合の数）とする。
ここで注意することは、区間$\ i\ $の柵の状態は無視することである。位置$\ i - 1\ $と$\ i\ $の間の位置$\ P_i\ $に置くボールの個数と、位置$\ i - 1\ $に柵を置くかどうかで場合分けをして遷移を考える。
まず位置$\ i - 1\ $に印がない場合を考える（すなわち柵を置いてもよいし置かなくても良い）。例えば$\ dp[i][0]\ $の値は次のようになる。
$\ i - 1\ $に柵を置く場合、$\ dp[i][0]\ += dp[i - 1][2]\ $（$\ P_i\ $にボールを置かない）
$\ i - 1\ $に柵を置かない場合、$\ dp[i][0]\ += dp[i - 1][0]\ $（$\ P_i\ $にボールを置かない）
つまり、常に上の$\ dp[i][j]\ $の条件に矛盾しないように、ボールを置いて考えればよい。同様にすると、次のようになる。
$\ i - 1\ $に柵を置く場合、$\ dp[i][1]\ += 2 * dp[i - 1][2]\ $（$\ P_i\ $にどちらかのボールを選んで置く）
$\ i - 1\ $に柵を置かない場合、$\ dp[i][1]\ += 2 * dp[i - 1][0]\ $（$\ P_i\ $にどちらかのボールを選んで置く）$+ dp[i - 1][1]\ $（$\ P_i\ $にボールを置かない）
$\ i - 1\ $に柵を置く場合、$\ dp[i][2]\ += dp[i - 1][2]\ $（$\ P_i\ $に両方のボールを置く）
$\ i - 1\ $に柵を置かない場合、$\ dp[i][2]\ += dp[i - 1][0]\ $（$\ P_i\ $に両方のボールを置く）$+ dp[i - 1][1]\ $（すでに置いてあるボールとは異なる色のボールを$\ P_i\ $に置く）$+ dp[i - 1][2]\ $（$\ P_i\ $に置かない）
以上から、次が従う。
$dp[i][0] = 1 * dp[i - 1][0] + 0 * dp[i - 1][1] + 1 * dp[i - 1][2]\ $
$dp[i][1] = 2 * dp[i - 1][0] + 1 * dp[i - 1][1] + 2 * dp[i - 1][2]\ $
$dp[i][2] = 1 * dp[i - 1][0] + 1 * dp[i - 1][1] + 2 * dp[i - 1][2]\ $
これは明らかに次のように書ける。
$
\left(
\begin{array}{rrr}
dp[i][0] \\
dp[i][1] \\
dp[i][2] \\
\end{array}
\right) = \left(
\begin{array}{rrr}
1 & 0 & 1 \\
2 & 1 & 2 \\
1 & 1 & 2 \\
\end{array}
\right) \left(
\begin{array}{rrr}
dp[i - 1][0] \\
dp[i - 1][1] \\
dp[i - 1][2] \\
\end{array}
\right)
$
次に位置$\ i - 1\ $に印がついている場合を考えると、その位置では柵が置けないため、上の場合分けにおける柵を置かない場合のみを考えることで
$dp[i][0] = 1 * dp[i - 1][0] + 0 * dp[i - 1][1] + 0 * dp[i - 1][2]\ $
$dp[i][1] = 2 * dp[i - 1][0] + 1 * dp[i - 1][1] + 0 * dp[i - 1][2]\ $
$dp[i][2] = 1 * dp[i - 1][0] + 1 * dp[i - 1][1] + 1 * dp[i - 1][2]\ $
であることがわかるため、以下のようになる。
$
\left(
\begin{array}{rrr}
dp[i][0] \\
dp[i][1] \\
dp[i][2] \\
\end{array}
\right) = \left(
\begin{array}{rrr}
1 & 0 & 0 \\
2 & 1 & 0 \\
1 & 1 & 1 \\
\end{array}
\right) \left(
\begin{array}{rrr}
dp[i - 1][0] \\
dp[i - 1][1] \\
dp[i - 1][2] \\
\end{array}
\right)
$
よって、各印の間は上の行列の累乗を用いて計算し、印の位置で下の行列を1回かけるということを繰り返せば高速に答えを求めることができる。
実装
#include "bits/stdc++.h" using namespace std; const int MOD = 1000000007; typedef long long Type; typedef vector<vector<Type>> Matrix; Matrix Mul(const Matrix &a, const Matrix &b) { assert(a[0].size() == b.size()); Matrix c(a.size(), vector<Type> (b[0].size())); for (int i = 0; i < a.size(); i ++) { for (int k = 0; k < b.size(); k ++) { for (int j = 0; j < b[0].size(); j ++) { c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD; } } } return c; } Matrix Pow(Matrix a, long long n) { assert(a.size() == a[0].size()); Matrix b(a.size(), vector<Type> (a.size())); for (int i = 0; i < a.size(); i ++) { b[i][i] = 1; } while (n > 0) { if (n & 1) b = Mul(b, a); a = Mul(a, a); n >>= 1; } return b; } int main() { int n, m, x; scanf("%d%d", &n, &m); Matrix a = {{1, 0, 0}, {2, 1, 0}, {1, 1, 1}}; Matrix b = {{1, 0, 1}, {2, 1, 2}, {1, 1, 2}}; Matrix ans = a; int prev = 1; while (m --) { scanf("%d", &x); ans = Mul(Pow(b, x - prev), ans); ans = Mul(a, ans); prev = x + 1; } ans = Mul(Pow(b, n - prev), ans); printf("%lld\n", ans[2][0]); return 0; }
DDCC C. グラフいじり
DDCC 2017 本戦 C. グラフいじり
C: グラフいじり - DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦 | AtCoder
感想
dfsの計算量を間違えていた。$\ O(m(n + m))\ $。これは$\ O(n^4)\ $なので、$\ TLE\ $する。仕方がないので無理やり通した。
解法
まずはある有向グラフが与えられたときに、それが条件（どのサイクルの距離の総和も$\ 0\ $であること）を満たしているかどうかを判定することを考える。条件を満たしているグラフの任意の異なる2点$\ S, T\ $を見ると、$\ S\ $から$\ T\ $に向かう任意のパスの距離はすべて一定になっているはずである。なぜなら、もし2つのパスが存在してその距離がそれぞれ$\ d_1, d_2\ (d_1 \neq d_2)\ $となっているならば、条件より存在する$\ T\ $から$\ S\ $へのある共通のパスを用いてサイクルを2つ作ると、これらの少なくとも一方の総和は$\ 0\ $でないので矛盾する。また、この距離を$\ d\ $とすると、$\ T\ $から$\ S\ $へのパスの距離は$\ -d\ $となっているはずである。そして逆に任意の2点についてこの距離の条件が成り立てば、条件を満たすことがわかる。これは簡単なdfsで求めることができる。計算量は$\ O(n)\ $である（これは嘘で、本当は$\ O(n + m) = O(m) = O(n^2)\ $）。
さて、次に長さを変える辺を一つ固定し、この繋いでいる頂点を$\ S \ $ -> $\ T\ $、その長さを$\ x\ $と仮定する。すると、まず必要条件として、上の条件と同じようなことを考えることができるはずであり、あるサイクルに関して総和が$\ 0\ $になるようにするための$\ x\ $が一意に定まるはずである。これを決めてしまえば、上で述べた判定によって、全体が条件を満たすかを判定すればよい。
従って、これをすべての辺についてチェックすればよい。この操作は$\ O(m)\ $でできるので、全体の計算量は$\ O(nm)\ $となるので十分高速である（これは嘘で、本当は$\ O(n^4)\ $なので、間に合わない）。
よって間に合わないことがわかるが、せっかく書いたので通したい。辺を順番に見ている場合でもほとんど通っているので、辺をランダムにシャッフルし、前半の$\ X\ $％だけ試す方針をとることにする。これはstd::shuffleを使うなどして実装する。辺が少ないときはすべて見てよいとし、辺数が$\ 50000\ $を超えるときは$\ 60\ $％、辺数が$\ 75000\ $を超えるときは$\ 35\ $％をみて、条件を満たすものが見つかるまで探索し、なければ即終了するという実装にすると、5回投げたら3回通るくらいの精度（？）になった。
実装
#include "bits/stdc++.h" using namespace std; #define mp make_pair static const long long INFL = 0x3f3f3f3f3f3f3f3fLL; long long dist[303]; vector<pair<int, long long>> g[303]; struct edge { int a, b; long long cost; }; void init() { for (int i = 0; i < 303; i ++) dist[i] = -INFL; } bool check(int v, int from, int to, long long x, long long d) { dist[v] = d; for (auto e : g[v]) { int u = e.first, cost = e.second; if (from == v && to == u) { assert(d == 0); if (!check(u, from, to, x, d + x)) return false; } else if (dist[u] == -INFL) { if (!check(u, from, to, x, d + cost)) return false; } else if (dist[u] != d + cost) { return false; } } return true; } long long get_x(int v, long long d) { dist[v] = d; for (auto e : g[v]) { int u =e.first, cost = e.second; if (dist[u] == -INFL) { long long x = get_x(u, d + cost); if (x != INFL) return x; } else if (dist[u] != d + cost) { return d + cost - dist[u]; } } return INFL; } int main() { int n, m; scanf("%d%d", &n, &m); vector<edge> es; for (int i = 0; i < m; i ++) { int a, b; long long c; scanf("%d%d%lld", &a, &b, &c); a --, b --; g[a].push_back(mp(b, c)); es.push_back((edge) {a, b, c} ); } //Randomly choose the edges random_device seed_gen; mt19937 engine(seed_gen()); shuffle(es.begin(), es.end(), engine); for (int i = 0; i < m; i ++) { if (m > 50000) if (i > (m * 60) / 100) break; if (m > 75000) if (i > (m * 35) / 100) break; edge e = es[i]; int v = e.a, u = e.b; long long cost = e.cost; init(); dist[v] = 0; long long x = get_x(u, 0); if (x == INFL) x = 0; init(); bool ans = check(v, v, u, -x, 0); if (ans) return !puts("Yes"); } return !puts("No"); }
Atcoder Grand Contest 013 E. Placing Squares
Atcoder Grand Contest 013 E. Placing Squares
E: Placing Squares - AtCoder Grand Contest 013 | AtCoder
感想
$\ O(n)\ $を高速化したかったけどできてない.....
想定解はまた今度考える。
解法
まず愚直に$\ DP\ $を書くと$\ O(n^2)\ $になる。この記事ではうまく高速化しないと通せない$\ O(n)\ $解法を説明する。印の処理は容易なので、省略する。
まず$\ dp_i = \sum_{k=0}^{i-1} dp_k * (i - k) ^ 2\ $という式を立てることができるのでこれを変形していく。
$\ dp_i = i^2 * \sum_{k=0}^{i-1} dp_k - 2i * \sum_{k=0}^{i-1} k * dp_k + \sum_{k=0}^{i-1} k^2 * dp_k\ $
$\ dp_i = i^2 * sum_{i-1} - 2 * i * sum2_{i-1} + sum3_{i-1}\ $とおくと
$\ sum_{i} = sum_{i-1} + dp_{i-1}\ $
$\ sum2_{i} = sum2_{i-1} + (i-1)*dp_{i-1}\ $
$\ sum3_{i} = sum3_{i-1} + (i-1)^2 * dp_{i-1}\ $
を用いて順番に計算していける。
ごちゃごちゃ書いたが、要するに総和を知りたいときに一つ前に使った総和そのものが使える典型パターンである。
よってこれは$\ O(n)\ $で計算できる。
さらにこれらは一つ前の情報しか必要としないので、すべて一つの変数を使いまわすことで空間計算量はマークの分の$\ O(n)\ $になる。
実装(5倍くらいTLE(>_<))
#include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; int main() { int n, m, x; scanf("%d%d", &n, &m); vector<bool> marked(n + 1, false); for (int i = 0; i < m; i ++) { scanf("%d", &x); marked[x] = true; } long long ans = 1; long long sum = 1, sum2 = 0, sum3 = 0; long long j = 0; for (long long i = 1; i <= n; i ++) { j += i * 2 - 1; //j = i * i j %= MOD; if (marked[i]) ans = 0; else { ans = j * sum - 2 * i * sum2 + sum3; ans %= MOD; sum += ans; sum2 += i * ans; sum3 += j * ans; sum %= MOD; sum2 %= MOD; sum3 %= MOD; } } printf("%lld\n", ((ans % MOD) + MOD) % MOD); return 0; }
Atcoder Regular Contest 084 F. XorShift
Atcoder Regular Contest 084 F. XorShift
F: XorShift - AtCoder Regular Contest 084 | AtCoder
解法
基底とする数は与えられる$\ n\ $個の数だけとして考えて良い。これらを任意の個数使って、シフトさせたり$\ xor\ $をとったりして数を作る。
ここで$\ xor\ $をとるという操作は、$\ mod\ 2\ $で各桁の差（あるいは和）をとるという操作に読み替えることができる。さらにシフトの操作を加えると、除算の筆算のような操作を繰り返していけることがわかる。
結局これらの操作によって作ることができる数というのは、これらの$\ gcd\ $の倍数全体であり、逆にそれ以外の数は作れないことが言える。これは整数で考えるとわかりやすくて、例えば$\ \{18, 42, 66\}\ $という数から適当な加減を繰り返すことによって$\ gcd(18, 42, 66) = 6\ $の倍数はすべて作ることができるし、逆にそれ以外はどうやっても作れない。
よって$\ n\ $個の数の$\ gcd\ $を求め、$\ X\ $以下の$\ gcd\ $の倍数の個数を求めればそれが答えである。 これはなんか頑張るとできる。
bitsetとvectorによる実装をどちらもした。bitsetの方が、$\ xor\ $の操作がわかりやすかったり、stringを経由しなくても数を扱えるという点で優れていると思うが、実質の長さを知りたいときや、大小比較をしたいときに少し不便だったり、慣れの問題だが先頭（左端）のインデックスが$\ size - 1\ $であるためバグる確率が高い感じがあった。
実装1（vectorによる）
#include "bits/stdc++.h" using namespace std; static const int MOD = 998244353; vector<int> BitsetGcd(vector<int> s, vector<int> t) { int n = s.size(), m = t.size(); if (n < m) return BitsetGcd(t, s); if (!m) return s; for (int i = 0; i < m; i ++) s[i] ^= t[i]; int p = n; for (int i = 0; i < n; i ++) { if (s[i]) { p = min(p, i); break; } } vector<int> a(n - p); for (int i = 0; i < n - p; i ++) a[i] = s[p + i]; return BitsetGcd(t, a); } long long ModPow(long long x, long long n, long long m) { long long res = 1; while (n > 0) { if (n & 1) res = res * x % m; x = x * x % m; n >>= 1; } return res; } int main() { int n; scanf("%d", &n); string x; cin >> x; vector<int> g; for (int i = 0; i < n; i ++) { string s; cin >> s; int k = s.size(); vector<int> b(k); for (int i = 0; i < k; i ++) b[i] = s[i] - '0'; g = BitsetGcd(g, b); } n = x.size(); vector<int> c(n), d(n); for (int i = 0; i < n; i ++) c[i] = x[i] - '0'; int m = g.size(); int ans = 0; for (int i = 0; i + m <= n; i ++) { if (c[i]) ans = (ans + ModPow(2, n - m - i, MOD)) % MOD; if (c[i] == d[i]) continue; for (int j = 0; j < m; j ++) d[i + j] ^= g[j]; } printf("%d\n", (ans + (d > c ? 0 : 1)) % MOD); return 0; }
実装2（bitsetによる）
#include "bits/stdc++.h" using namespace std; static const int MOD = 998244353; #define N 4040 int Len(const bitset<N> &a) { for (int res = N - 1; res >= 0; res --) { if (a[res]) return res + 1; } return 0; } bitset<N> gcd(bitset<N> s, bitset<N> t) { int n = Len(s), m = Len(t); if (n < m) return gcd(t, s); if (t.none()) return s; int d = n - m; bitset<N> u = t; u <<= d; s ^= u; return gcd(t, s); } long long ModPow(long long x, long long n, long long m) { long long res = 1; while (n > 0) { if (n & 1) res = res * x % m; x = x * x % m; n >>= 1; } return res; } int main() { int q; scanf("%d", &q); bitset<N> x; cin >> x; bitset<N> g; for (int i = 0; i < q; i ++) { bitset<N> s; cin >> s; g = gcd(g, s); } int n = Len(x); bitset<N> d(0); int m = Len(g); int ans = 0; for (int i = n - 1; i >= m - 1; i --) { if (x[i]) ans = (ans + ModPow(2, i - m + 1, MOD)) % MOD; if (x[i] == d[i]) continue; d ^= (g << i - m + 1); } bool ok = true; for (int i = n - 1; i >= 0; i --) { if (d[i] < x[i]) break; if (d[i] > x[i]) ok = false; } printf("%d\n", (ans + ok) % MOD); return 0; }
Atcoder Grand Contest 007 F. Shik and Copying String
Atcoder Grand Contest 007 F. Shik and Copying String
F: Shik and Copying String - AtCoder Grand Contest 007 | AtCoder
感想
考えることはシンプルなんだけど条件が難しい
解法
$\ T\ $の連続する文字の先頭文字と、それに対応する$\ S\ $の文字を決定できる。これがうまく対応させられないときは構成不可能で、逆に対応させることができれば構成可能である。
これらを$\ s + 1\ $回以下の操作で構成できるための条件は、$\ S\ $と$\ T\ $の対応する位置を$\ a\ $と$\ b\ $で表すと、任意の$\ i\ $について、$\ a_{i + s} - s \geq b_i\ $が成り立つことである。よってこれは二分探索で求めることができる。この条件は、絵を書いて$\ 1\ $時間くらいにらめば思いつく（ほんまか？）。
実装
#include "bits/stdc++.h" using namespace std; int main() { int n; scanf("%d", &n); string s, t; cin >> s >> t; if (s == t) return !puts("0"); if (s[0] != t[0]) return !puts("-1"); vector<int> a, b; b.push_back(0); for (int i = 1; i < n; i ++) if (t[i] != t[i - 1]) b.push_back(i); int k = b.size(); int p = n - 1; int bp = k - 1; while (p > 0) { while (t[b[bp]] != s[p]) p --; if (p == 0) break; a.push_back(p); bp --; p = min(p, b[bp]); } a.push_back(0); reverse(a.begin(), a.end()); if (a.size() != k) return !puts("-1"); int lb = -1, ub = k; while (ub - lb > 1) { int s = (lb + ub) / 2; bool ok = true; for (int i = 0; i < k; i ++) { if (i + s < k) ok &= a[i + s] - s >= b[i]; } if (ok) ub = s; else lb = s; } printf("%d\n", ub + 1); return 0; }
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; }
