No.930 数列圧縮

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.930 数列圧縮

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題（複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 137
作問者 :

chocorusk / テスター :

risujiroh

22 ProblemId : 2878 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2019-11-19 22:00:21

問題文

yuki君は長さ $N$ の数列 $a$ を持っています。 $a$ は $1, 2, \dots, N$ の順列です。yuki君は数列に次のような操作を行うことができます。

数列の隣りあう $2$ つの要素であって、(左の要素) $<$ (右の要素) を満たすものを選び、そのどちらか一方を削除する。

数列

a

に

N - 1

回操作を行って数列の長さを

1

にすることができるか判定し、できるならその手順をひとつ求めてください。

入力

 $N$ 
 $a_{1} a_{2} \dots a_{N}$

$2 \leq N \leq 10^{5}$
$1 \leq a_{i} \leq N$
$i \neq j$ のとき $a_{i} \neq a_{j}$
入力はすべて整数である。

出力

操作により数列の長さを $1$ にすることが不可能なら、Noと出力せよ。可能なら、 $1$ 行目にYesと出力し、 $2$ 行目に $N - 1$ 個の整数を空白区切りで出力せよ。 $i$ 個目の整数は、 $i$ 回目の操作で削除する数でなければならない。複数の手順が考えられる場合、どれを出力してもよい。

サンプル

サンプル1

入力

4
2 3 1 4

出力

Yes
2 1 4

隣りあう $2$ つの要素 $(2, 3)$ を選び、 $2$ を削除します。数列は $(3, 1, 4)$ となります。
隣りあう $2$ つの要素 $(1, 4)$ を選び、 $1$ を削除します。数列は $(3, 4)$ となります。
隣りあう $2$ つの要素 $(3, 4)$ を選び、 $4$ を削除します。数列は $(3)$ となります。

サンプル2

入力

5
5 4 2 3 1

出力

No

最初に行える操作は、隣りあう $2$ つの要素 $(2, 3)$ を選び、 $2$ または $3$ を削除する操作のみです。
最初に $2$ を削除すると、数列は $(5, 4, 3, 1)$ となり、これ以上操作を行えません。
最初に $3$ を削除すると、数列は $(5, 4, 2, 1)$ となり、これ以上操作を行えません。

よって、数列の長さを

1

にすることは不可能です。

サンプル3

入力

6
3 6 2 5 1 4

出力

Yes
1 5 6 2 4

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

yukicoder

No.930 数列圧縮

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力