問題一覧 > 通常問題

No.930 数列圧縮

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 135
作問者 : chocoruskchocorusk / テスター : risujirohrisujiroh
21 ProblemId : 2878 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-11-19 22:00:21

問題文

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

  • 数列の隣りあう $2$ つの要素であって、(左の要素)$<$(右の要素) を満たすものを選び、そのどちらか一方を削除する。
数列 $a$ に $N-1$ 回操作を行って数列の長さを $1$ にすることができるか判定し、できるならその手順をひとつ求めてください。

入力

$N$
$a_1\ a_2\ \ldots \ 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もしくは右上の雲マークをクリックしてアカウントを作成してください。