D - 円卓の席順 / Seating Order at the Round Table 解説 by admin
gpt-5.5-xhigh概要
各席のスコアそのものではなく、まず「隣同士の大小関係」だけを決めます。
その大小関係に矛盾がなければ、トポロジカルソート順に \(1,2,\ldots,N\) を割り当てることで条件を満たす順列を作れます。
考察
重要なのは、各席の具体的なスコアではなく、隣接する席同士でどちらが小さいかです。
席 \(i\) と席 \(i+1\) の大小関係を表す値 \(S_i\) を考えます。
ただし、\(i=N\) のとき席 \(N+1\) は席 \(1\) とします。
\(S_i\) を次のように定義します。
- \(S_i = 1\) : \(P_i < P_{i+1}\)
- \(S_i = 0\) : \(P_i > P_{i+1}\)
このとき、席 \(i\) の左右の隣について考えます。
左隣 \(i-1\) が自分より小さい
\(\iff P_{i-1} < P_i\)
\(\iff S_{i-1} = 1\)右隣 \(i+1\) が自分より小さい
\(\iff P_{i+1} < P_i\)
\(\iff S_i = 0\)
したがって、
[ Ai = [S{i-1}=1] + [S_i=0] ]
となります。
ここから、\(A_i\) の値ごとに \(S_i\) がどう決まるか分かります。
| \(A_i\) | 必要な条件 |
|---|---|
| \(0\) | \(S_{i-1}=0,\ S_i=1\) |
| \(1\) | \(S_i=S_{i-1}\) |
| \(2\) | \(S_{i-1}=1,\ S_i=0\) |
つまり、直前の値 \(S_{i-1}\) が分かれば、\(S_i\) は一意に決まります。
ただし円環なので、最初に使う \(S_N\) が分かりません。
そこで \(S_N=0\) と仮定する場合、\(S_N=1\) と仮定する場合の高々 \(2\) 通りを試せば十分です。
素朴に順列 \(P\) を全探索すると \(N!\) 通りあり、\(N \leq 5 \times 10^5\) では到底間に合いません。
また、局所的に小さい値・大きい値を置いていく貪欲法では、大小関係が円環全体で矛盾していないかを見落とす可能性があります。
そこで、まず隣同士の大小関係を有向辺として表し、それが矛盾しないかをトポロジカルソートで判定します。
アルゴリズム
1. 大小関係 \(S\) を構築する
\(S_N\) の初期値を \(0\) または \(1\) と仮定して、順に \(S_1,S_2,\ldots,S_N\) を決めます。
現在 \(S_{i-1}\) が prev として分かっているとします。
\(A_i=0\) のとき
- 必ず \(S_{i-1}=0\) でなければならない
- そのうえで \(S_i=1\)
\(A_i=1\) のとき
- \(S_i=S_{i-1}\)
\(A_i=2\) のとき
- 必ず \(S_{i-1}=1\) でなければならない
- そのうえで \(S_i=0\)
最後に、求めた \(S_N\) が最初に仮定した値と一致していなければ、円環として矛盾しています。
両方の初期値を試しても構築できなければ、答えは存在しません。
2. 大小関係を有向グラフにする
各隣接辺について、小さい方から大きい方へ有向辺を張ります。
具体的には、席 \(i\) と席 \(i+1\) について、
- \(S_i=1\) なら \(P_i < P_{i+1}\) なので、辺 \(i \to i+1\)
- \(S_i=0\) なら \(P_i > P_{i+1}\) なので、辺 \(i+1 \to i\)
を張ります。
この有向グラフにサイクルがあると、
[ P_{v1} < P{v2} < \cdots < P{vk} < P{v_1} ]
のような矛盾が発生するため、順列は作れません。
3. トポロジカルソートする
作った有向グラフに対してトポロジカルソートを行います。
全頂点を並べられなかった場合
有向サイクルがあるので-1全頂点を並べられた場合
トポロジカル順に小さい値を割り当てます。
例えば、トポロジカル順が
[ v_1, v_2, \ldots, v_N ]
なら、
[ P_{v1}=1,\ P{v2}=2,\ \ldots,\ P{v_N}=N ]
とします。
有向辺は必ず「小さい方から大きい方」へ張っているので、この割り当てにより全ての隣接大小関係が満たされます。
その結果、各席の条件 \(A_i\) も満たされます。
計算量
- 時間計算量: \(O(N)\)
- 空間計算量: \(O(N)\)
大小関係 \(S\) の構築、グラフの構築、トポロジカルソートのいずれも線形時間で行えます。
実装のポイント
円環なので、添字は
(i + 1) % Nのように扱います。build(start)では、startを最後の辺 \(S_N\) とみなして処理します。最後に求めた値が
startと一致するかを確認することで、円環として整合しているか判定できます。有向グラフの各頂点の出次数は最大 \(2\) なので、隣接リストは軽量に持てます。
トポロジカルソートで得た順番に \(1,2,\ldots,N\) を割り当てれば、重複のない順列になります。
ソースコード
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<int> A(N);
for (int i = 0; i < N; i++) cin >> A[i];
vector<int> S;
auto build = [&](int start) -> bool {
vector<int> t(N);
int prv = start;
for (int i = 0; i < N; i++) {
int cur;
if (A[i] == 0) {
if (prv != 0) return false;
cur = 1;
} else if (A[i] == 1) {
cur = prv;
} else if (A[i] == 2) {
if (prv != 1) return false;
cur = 0;
} else {
return false;
}
t[i] = cur;
prv = cur;
}
if (prv != start) return false;
S = move(t);
return true;
};
if (!build(0) && !build(1)) {
cout << -1 << '\n';
return 0;
}
vector<array<int, 2>> adj(N);
vector<int> outdeg(N, 0), indeg(N, 0);
auto add_edge = [&](int u, int v) {
adj[u][outdeg[u]++] = v;
indeg[v]++;
};
for (int i = 0; i < N; i++) {
int j = (i + 1) % N;
if (S[i] == 1) {
add_edge(i, j);
} else {
add_edge(j, i);
}
}
vector<int> order;
order.reserve(N);
for (int i = 0; i < N; i++) {
if (indeg[i] == 0) order.push_back(i);
}
for (size_t head = 0; head < order.size(); head++) {
int v = order[head];
for (int k = 0; k < outdeg[v]; k++) {
int to = adj[v][k];
if (--indeg[to] == 0) order.push_back(to);
}
}
if ((int)order.size() != N) {
cout << -1 << '\n';
return 0;
}
vector<int> P(N);
for (int i = 0; i < N; i++) {
P[order[i]] = i + 1;
}
for (int i = 0; i < N; i++) {
if (i) cout << ' ';
cout << P[i];
}
cout << '\n';
return 0;
}
この解説は gpt-5.5-xhigh によって生成されました。