問題一覧 > 通常問題

No.3287 Golden Ring

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 72
作問者 : kona0001 / テスター : tobisatis RyosukeFukatani koba-e964 ir5 drken1215
ProblemId : 12632 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-10-03 00:12:21

問題文

円環上に並んだ長さ $2$ 以上の配列に対し、「どの隣接する要素の和を見ても同じものが存在しない」ものを黄金環と定義します。 すなわち、以下の条件をすべて満たした配列 $A$ は黄金環です。

  • $2 \le N$
  • $A$ は長さ $N$ の配列
  • $S_i = A_i + A_{i+1}$ $(1 \le i \le N-1)$
  • $S_N = A_N + A_1$
  • $i \ne j$ ならば $S_i \ne S_j$

$1$ から $N$ まで並べた配列 $(1,2,...,N)$ が与えられます。この配列を自由に並び替えることで、黄金環を作ることができるか判定してください。できる場合は、その配列を求めてください。

制約

  • $2 \le N \le 2000$
  • $N$ は整数

入力

入力は以下の形式で標準入力から与えられます。

$N$

出力

黄金環となる配列 $A$ を作れる場合は、答えを以下の形式で出力してください。

Yes
$A_1\ A_2 \ldots\ A_N$

解が複数存在する場合、どれを出力しても正解とみなされます。

できない場合はNoを出力してください。最後に改行してください。

サンプル

サンプル1
入力
4
出力
Yes
1 3 4 2

$A=(1,3,4,2)$ と並び替えることで、隣接する要素の和はそれぞれ $1+3=4$、$3+4=7$、$4+2=6$、$2+1=3$ となり $S=(4,7,6,3)$ となります。 $S$ 内で重複する値がないため、この配列は黄金環です。

他にも例えば $A=(4,2,1,3)$ は条件を満たすため、正解となります。

$A=(1,2,3,4)$ とした場合、$S=(3,5,7,5)$ となり値が重複してしまうため、不正解となります。

サンプル2
入力
5
出力
Yes
2 4 5 3 1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。