No.1804 Intersection of LIS

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

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

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 59
作問者 :

NatsubiSogan / テスター :

nok0

penguinman

3 ProblemId : 7029 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2021-11-17 20:14:24

$(1, 2, \dots, N)$ を並び替えた数列 $P = (P_{1}, P_{2}, \dots, P_{N})$ が与えられます。 $P$ の LIS（最長増加部分列）として考えられるものはいくつかありますが、その すべて に含まれる要素を列挙してください。

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

まず、 $1$ 行目に、 $P$ のすべての LIS に含まれる要素の個数を出力してください。

その後、 $2$ 行目に、 $P$ のすべての LIS に含まれる要素を、添え字の昇順に 空白区切りで出力してください。なお、要素数が $0$ の場合は、 $2$ 行目に空行を出力してください。

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

5
1 4 3 2 5

2
1 5

LIS として考えられるものは、 $(A_{1}, A_{2}, A_{5}) = (1, 4, 5), (A_{1}, A_{3}, A_{5}) = (1, 3, 5), (A_{1}, A_{4}, A_{5}) = (1, 2, 5)$ の $3$ つです。

これらのいずれにも含まれるのは $A_{1} = 1, A_{5} = 5$ なので、これらを出力します。

3
2 3 1

2
2 3

LIS は $(A_{1}, A_{2}) = (2, 3)$ のみです。

6
4 5 6 1 2 3

すべての LIS に含まれる要素の数が $0$ である場合もあります。このような場合において、 $2$ 行目は空行として出力することを忘れないで下さい。

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