概要

隣同士の大小関係だけを先に決め、その大小関係を満たすように \(1\) から \(N\) の順位を割り当てます。

具体的には、円周上の各辺に「どちらの席のスコアが小さいか」という向きを付け、その後トポロジカルソートで実際の順列 \(P\) を作ります。

考察

各席の条件は、実際の値 \(P_i\) そのものではなく、隣の席との大小関係だけで決まります。

そこで、隣接する席 \(i\) と \(i+1\) の大小関係を次のように表します。

• \(s_i = 1\) : \(P_i < P_{i+1}\)
• \(s_i = 0\) : \(P_i > P_{i+1}\)

ただし、\(P_{N+1} = P_1\) とします。

このとき、席 \(i\) について考えます。

• 左隣 \(i-1\) のスコアが \(P_i\) より小さい
  \(\Leftrightarrow P_{i-1} < P_i\)
  \(\Leftrightarrow s_{i-1} = 1\)

• 右隣 \(i+1\) のスコアが \(P_i\) より小さい
  \(\Leftrightarrow P_{i+1} < P_i\)
  \(\Leftrightarrow s_i = 0\)

したがって、

\[ A_i = [s_{i-1} = 1] + [s_i = 0] \]

が成り立ちます。

ここで \(s_{i-1}\) が分かっていると、\(A_i\) から \(s_i\) は一意に決まります。

\(A_i\)	必要な条件	\(s_i\)
\(0\)	\(s_{i-1}=0,\ s_i=1\)	\(1\)
\(1\)	\((s_{i-1},s_i)=(0,0)\) または \((1,1)\)	\(s_{i-1}\)
\(2\)	\(s_{i-1}=1,\ s_i=0\)	\(0\)

つまり、最初の \(s_N\) を決めれば、\(s_1,s_2,\ldots,s_N\) は順番に決まります。

ただし円なので、最後に得られる \(s_N\) が最初に仮定した値と一致していなければなりません。

最初の \(s_N\) は \(0\) または \(1\) のどちらかなので、両方を試せば十分です。

---

次に、大小関係 \(s\) が決まったとしても、実際に順列 \(P\) が存在するとは限りません。

例えば、すべての辺で

\[ P_1 < P_2 < \cdots < P_N < P_1 \]

のような循環した大小関係ができると不可能です。

そこで、大小関係を有向グラフとして見ます。

• \(P_i < P_{i+1}\) なら、辺 \(i \to i+1\)
• \(P_i > P_{i+1}\) なら、辺 \(i+1 \to i\)

つまり、「小さい方から大きい方へ」辺を張ります。

この有向グラフが DAG なら、トポロジカル順に \(1,2,\ldots,N\) を割り当てれば条件を満たす順列になります。

逆に、有向閉路がある場合は大小関係が矛盾するため不可能です。

アルゴリズム

1. \(s_N\) を \(0\) と仮定して、\(s_1,s_2,\ldots,s_N\) を順に決める。
2. 矛盾した場合は、\(s_N\) を \(1\) と仮定して同様に試す。
3. どちらでも矛盾する場合は -1。
4. 得られた \(s\) から有向グラフを考える。
   • \(s_i=1\) なら \(i \to i+1\)
   • \(s_i=0\) なら \(i+1 \to i\)
5. 各頂点の入次数はちょうど \(A_i\) になるので、入次数 \(0\) の頂点からトポロジカルソートする。
6. 頂点を取り出した順に \(1,2,\ldots,N\) を割り当てる。
7. 全頂点を処理できれば答えを出力し、できなければ -1。

例として、\(N=4,\ A=(0,1,2,1)\) の場合を考えます。

\(s_4=0\) として始めると、

\[ s=(1,1,0,0) \]

が得られます。

これは、

\[ P_1<P_2,\quad P_2<P_3,\quad P_4<P_3,\quad P_1<P_4 \]

を意味します。

例えばトポロジカル順として \(1,2,4,3\) が取れるので、

\[ P=(1,2,4,3) \]

とすれば条件を満たします。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 配列はコード上では \(0\)-indexed で扱っています。

• 円環なので、左隣や右隣を求めるときは添字を巡回させる必要があります。

• トポロジカルソートでは、各頂点の出辺は高々 \(2\) 本です。

  • 左隣へ辺があるのは \(s_{v-1}=0\) のとき
  • 右隣へ辺があるのは \(s_v=1\) のとき

• pop(0) は \(O(N)\) かかるため、キューはリストと head 変数で管理しています。

• コードでは indeg = A として、\(A\) を入次数配列としてそのまま再利用しています。元の \(A\) は以後使わないため問題ありません。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N = int(input())
    A = list(map(int, input().split()))

    def build(start):
        s = [0] * N
        prev = start
        for i, a in enumerate(A):
            if a == 0:
                if prev != 0:
                    return None
                cur = 1
            elif a == 1:
                cur = prev
            else:
                if prev != 1:
                    return None
                cur = 0
            s[i] = cur
            prev = cur
        if prev != start:
            return None
        return s

    s = build(0)
    if s is None:
        s = build(1)
    if s is None:
        print(-1)
        return

    indeg = A
    q = [i for i, a in enumerate(indeg) if a == 0]
    ans = [0] * N

    head = 0
    rank = 1
    append = q.append

    while head < len(q):
        v = q[head]
        head += 1
        ans[v] = rank
        rank += 1

        left = v - 1
        if left < 0:
            left = N - 1
        if s[left] == 0:
            indeg[left] -= 1
            if indeg[left] == 0:
                append(left)

        if s[v] == 1:
            right = v + 1
            if right == N:
                right = 0
            indeg[right] -= 1
            if indeg[right] == 0:
                append(right)

    if rank != N + 1:
        print(-1)
    else:
        sys.stdout.write(" ".join(map(str, ans)))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。