概要

円卓に並んだ \(N\) 個の席に \(1\) から \(N\) のスコアを割り当て、各席について「隣り合う席のうち自分よりスコアが低い席の数」が与えられた条件 \(A_i\) と一致するような順列を求める問題です。隣接関係を不等号の向き（向き付きの辺）として捉えることで、トポロジカルソートの問題に帰着させることができます。

考察

1. 隣接する席との大小関係を定義する

席 \(i\) と席 \(i+1\) のスコアの大小関係を \(d_i\) と定義します（インデックスは \(N\) を法とする）。 - \(P_i < P_{i+1}\) のとき、\(d_i = 1\) - \(P_i > P_{i+1}\) のとき、\(d_i = -1\)

このとき、各席 \(i\) において「隣の席のうちスコアが自分より小さい席」の条件は以下のように表せます。 - 席 \(i-1\) が自分より小さい \(\iff P_{i-1} < P_i \iff d_{i-1} = 1\) - 席 \(i+1\) が自分より小さい \(\iff P_{i+1} < P_i \iff d_i = -1\)

したがって、条件 \(A_i\) は以下の式のようになります。 $\(A_i = (\text{if } d_{i-1} = 1 \text{ then } 1 \text{ else } 0) + (\text{if } d_i = -1 \text{ then } 1 \text{ else } 0)\)$

2. \(A_i\) の値による \(d_i\) の確定

\(A_i\) の値（0, 1, 2）に応じて、隣接する関係 \(d_{i-1}\) と \(d_i\) について以下のことが言えます。

• \(A_i = 0\) の場合： \(d_{i-1} = -1\) かつ \(d_i = 1\) である必要があります。 （席 \(i\) は局所的な最小値：\(P_{i-1} > P_i < P_{i+1}\)）
• \(A_i = 2\) の場合： \(d_{i-1} = 1\) かつ \(d_i = -1\) である必要があります。 （席 \(i\) は局所的な最大値：\(P_{i-1} < P_i > P_{i+1}\)）
• \(A_i = 1\) の場合： \((d_{i-1}, d_i)\) は \((1, 1)\) または \((-1, -1)\) のいずれかです。 つまり、\(d_i = d_{i-1}\) でなければなりません。 （席 \(i\) は単調増加または減少の途中：\(P_{i-1} < P_i < P_{i+1}\) または \(P_{i-1} > P_i > P_{i+1}\)）

3. 解の存在判定と構築

もし全ての \(A_i\) が \(1\) であれば、すべての \(d_i\) が等しくなります。これは \(P_1 < P_2 < \dots < P_N < P_1\)（またはその逆）を意味し、円環上では矛盾するため解は存在しません。

少なくとも一つの \(A_i\) が \(0\) または \(2\) であれば、そこを起点にすべての \(d_i\) を一意に決定できます。決定した \(d_i\) がすべての \(A_i\) の条件を満たしているかを確認し、矛盾がなければ、それらの大小関係を向き付きの辺としたグラフを構築します。

このグラフが閉路を持たなければ（DAGであれば）、トポロジカルソートによってスコア \(1 \dots N\) を割り振る順番を決定できます。

アルゴリズム

1. 起点の探索: \(A_i \in \{0, 2\}\) となる席 \(i\) を探す。見つからなければ -1 を出力。
2. 関係 \(d_i\) の決定:
   • 起点となる席 \(i\) について、\(A_i\) から \(d_{i-1}\) と \(d_i\) を決める。
   • そこから時計回りに、各 \(j\) について \(A_j\) を用いて \(d_j\) を順次決定していく。
3. 矛盾チェック: 決定した \(d\) の集合が、すべての \(A_i\) の条件と矛盾しないか確認する。矛盾があれば -1。
4. グラフ構築とトポロジカルソート:
   • \(d_i = 1\) なら 席 \(i \to\) 席 \(i+1\) の辺を張る。
   • \(d_i = -1\) なら 席 \(i+1 \to\) 席 \(i\) の辺を張る。
   • 入次数 \(0\) のノードから順にキューに入れる Kahn のアルゴリズムなどでトポロジカルソートを行う。
5. 結果の出力: トポロジカル順序に従って \(1, 2, \dots, N\) のスコアを割り当てる。閉路が存在（ソート結果が \(N\) 要素未満）した場合は -1。

計算量

• 時間計算量: \(O(N)\)
  • \(d_i\) の決定、矛盾チェック、トポロジカルソートの各工程がすべて \(O(N)\) で行えます。
• 空間計算量: \(O(N)\)
  • 隣接リストやトポロジカルソート用の配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 円環の扱い: インデックスの計算には (i + 1) % N や (i - 1 + N) % N を使用して、範囲外にならないよう注意します。

• トポロジカルソート: グラフの構築時に、辺の向きを「小さい方から大きい方へ」固定することで、ソート順がそのままスコアの昇順（\(1, 2, \dots, N\)）に対応するようにします。

  ソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

/**
 * Problem Analysis:
 * For each seat i, let d[i] represent the relationship between P[i] and P[i+1].
 * Define d[i] = 1 if P[i] < P[i+1] and d[i] = -1 if P[i] > P[i+1].
 * All indices are taken modulo N.
 * The number of neighbors of seat i with score smaller than P[i], denoted as A[i], is:
 * A[i] = (d[i-1] == 1 ? 1 : 0) + (d[i] == -1 ? 1 : 0).
 * 
 * From this, we can deduce:
 * - If A[i] = 0, then d[i-1] = -1 and d[i] = 1.
 * - If A[i] = 2, then d[i-1] = 1 and d[i] = -1.
 * - If A[i] = 1, then d[i] must be equal to d[i-1].
 * 
 * If all A[i] = 1, no solution exists because a circular sequence cannot be strictly monotonic.
 * Otherwise, we can determine all d[i] values and check for consistency.
 * If consistent, the relationships P[i] < P[i+1] or P[i] > P[i+1] form a Directed Acyclic Graph (DAG).
 * Any topological sort of this DAG gives an ordering for the scores P.
 */

int main() {
    // Optimize I/O operations
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;

    vector<int> A(N);
    int start_node = -1;
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        // Identify a seat that must be a local minimum or maximum
        if (A[i] == 0 || A[i] == 2) {
            start_node = i;
        }
    }

    // If all A[i] are 1, no solution exists
    if (start_node == -1) {
        cout << -1 << endl;
        return 0;
    }

    // Determine the relative order sequence d
    vector<int> d(N);
    // Initialize d[start_node-1] based on A[start_node]
    if (A[start_node] == 0) {
        d[(start_node - 1 + N) % N] = -1;
    } else {
        d[(start_node - 1 + N) % N] = 1;
    }

    // Propagate d values around the circle
    for (int k = 0; k < N; ++k) {
        int j = (start_node + k) % N;
        int prev = (j - 1 + N) % N;
        if (A[j] == 0) {
            d[j] = 1;
        } else if (A[j] == 2) {
            d[j] = -1;
        } else {
            // If A[j] == 1, d[j] must match d[prev]
            d[j] = d[prev];
        }
    }

    // Verify if the generated sequence d is consistent with all A[i]
    for (int j = 0; j < N; ++j) {
        int prev = (j - 1 + N) % N;
        int count = (d[prev] == 1) + (d[j] == -1);
        if (count != A[j]) {
            cout << -1 << endl;
            return 0;
        }
    }

    // Build the Directed Acyclic Graph based on d
    vector<vector<int>> adj(N);
    vector<int> in_degree(N, 0);
    for (int i = 0; i < N; ++i) {
        int u = i;
        int v = (i + 1) % N;
        if (d[i] == 1) { // P[i] < P[i+1]
            adj[u].push_back(v);
            in_degree[v]++;
        } else { // P[i] > P[i+1]
            adj[v].push_back(u);
            in_degree[u]++;
        }
    }

    // Perform topological sort (Kahn's algorithm)
    queue<int> q;
    for (int i = 0; i < N; ++i) {
        if (in_degree[i] == 0) q.push(i);
    }

    vector<int> topo;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo.push_back(u);
        for (int v : adj[u]) {
            if (--in_degree[v] == 0) q.push(v);
        }
    }

    // Check if a valid topological sort exists for all nodes
    if (topo.size() < (size_t)N) {
        cout << -1 << endl;
    } else {
        // Assign scores 1 to N based on the topological order
        vector<int> P(N);
        for (int i = 0; i < N; ++i) {
            P[topo[i]] = i + 1;
        }
        // Output the resulting permutation
        for (int i = 0; i < N; ++i) {
            cout << P[i] << (i == N - 1 ? "" : " ");
        }
        cout << endl;
    }

    return 0;
}

---

この解説は gemini-3-flash-thinking によって生成されました。