問題一覧 > 教育的問題

No.3489 あみだくじ作り

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 41
作問者 : 👑 p-adic
ProblemId : 9066 / yukicoder contest 496 (順位表) / 自分の提出
問題文最終更新日: 2026-04-03 21:43:33
yukicoder contest 496の他の問題:

問題文

入力に $2$ 以上の整数 $N$ と $N$ 以下の正整数からなる長さ $N$ の順列 $P$ が与えられます。

縦方向に下る形式のあみだくじ $A$ であって以下の条件を全て満たすものが存在するか否かを判定してください:

  1. $A$ は縦線をちょうど $N$ 本持つ。(それらは互いに平行である)
  2. $A$ は横線を高々 $N^2$ 本持つ。(それらは縦線と垂直で、互いに平行で、かつ上下位置が互いに異なる)
  3. $N$ 以下の任意の正整数 $i$ に対し、$A$ の左から $i$ 本目の縦線の最上部から始めてあみだくじのルールに従って線を下へ辿ると $A$ の左から $P_i$ 本目の縦線の最下部に到達する。

ただし $P_i$ で $P$ の $i$ 個目の成分を表します。

入力

入力は次の形式で標準入力から $2$ 行で与えられます:

  • $1$ 行目に $N$ が与えられます。
  • $2$ 行目に $N$ 以下の各正整数 $i$ に対する $P_i$ が $i$ の小さい順に半角空白区切りで与えられます。
$N$
$P_1$ $\cdots$ $P_N$

制約

入力は以下の制約を満たします:

  • $N$ は $2 \leq N \leq 100$ を満たす整数である。
  • $P$ は $N$ 以下の正整数からなる長さ $N$ の順列である。

出力

条件を満たすあみだくじ $A$ が存在しない場合はNoと出力してください。

存在する場合はそのような $A$ を $1$ つ選んでください。$A$ の横線の本数を $M$ と置き、$M$ 以下の各正整数 $j$ に対し $A$ の上から $j$ 本目の横線が $A$ の左から $i_j$ 本目の縦線と左から $i_j + 1$本目の縦線を結ぶように $N$ 未満の正整数 $i_j$ を定めます。次の形式で出力してください:

  • $1$ 行目にYesと出力してください。
  • $2$ 行目に $M$ を出力してください。
  • $M$ 以下の各正整数 $j$ に対し $2 + j$ 行目に $i_j$ を出力してください。

最後に改行してください。

なおこの問題はスペシャルジャッジ問題です。正解は $1$ つとは限りませんが、 $1$ つだけ出力してください。

ただし出力は上述した形式に厳格に従ってください。例えば余計な空白がある場合のジャッジの挙動は保証されません。

サンプル

サンプル1
入力
2
1 2
出力
Yes
0

縦線が $2$ 本、横線が $0$ 本のあみだくじが条件を満たします。この他にも

Yes
2
1
1

などが正解となります。一方で

Yes
6
1
1
1
1
1
1

正解でないことに注意してください。この例は横線が高々 $N^2 = 4$ 本しかないという条件を満たしていません。

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

縦線が $2$ 本で、横線が $1$ 本で、上から $1$ 本目の横線が左から $1$ 本目の縦線と左から $2$ 本目の縦線を結ぶあみだくじが条件を満たします。

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

縦線が $3$ 本で、横線が $2$ 本で、

  • 上から $1$ 本目の横線が左から $1$ 本目の縦線と左から $2$ 本目の縦線を結ぶ。
  • 上から $2$ 本目の横線が左から $2$ 本目の縦線と左から $3$ 本目の縦線を結ぶ。

とすることで得られるあみだくじが条件を満たします。

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