No.3477 Yet Another LIS Triangle
タグ : / 解いたユーザー数 32
作問者 : 👑
AngrySadEight
/ テスター :
kidodesu
問題文
整数を三角形状に並べて $3$ つの数列を作り,それらの数列の LIS の長さを全て一定の値にしてみましょう.
次の条件を全て満たす $3$ つの整数列 $A, B, C$ が存在するか判定し,存在する場合は例を $1$ つ示してください.
- $A, B, C$ の長さは全て $N$ である
- $A, B, C$ の最長増加部分列 (LIS) の長さは全て $K$ である
- $A_N = B_1$
- $B_N = C_1$
- $C_N = A_1$
- 長さ $3N - 3$ の数列 $P$ を,$P = \{A_1, A_2, \dots, A_{N - 1}, B_1, B_2, \dots, B_{N - 1}, C_1, C_2, \dots, C_{N - 1}\}$ と定める.このとき,数列 $P$ には $1$ 以上 $3N - 3$ 以下の整数が $1$ つずつ含まれる.
$T$ 個のテストケースが与えられるので,それぞれについて答えてください.
制約
- $T \geq 1$
- $2 \leq N \leq 10^5$
- $1 \leq K \leq N$
- $1$ つの入力ファイルに対する $N$ の総和は $10^5$ 以下
入力
入力は以下の形式で標準入力から与えられる.ここで,$\mathrm{case}_i(1 \leq i \leq T)$ は $i$ 番目のテストケースを表す.
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
各ケースは以下の形式で与えられる.
$N$ $K$
出力
各テストケースに対して,条件を満たす整数列 $A, B, C$ が存在しない場合は No と出力し,最後に改行せよ.存在する場合は,次の形式で整数列 $A, B, C$ を出力したのち,最後に改行せよ.条件を満たす整数列 $A, B, C$ が複数存在する場合は,そのいずれを答えても正解となる.
Yes $A_1$ $A_2$ $\dots$ $A_N$ $B_1$ $B_2$ $\dots$ $B_N$ $C_1$ $C_2$ $\dots$ $C_N$
サンプル
サンプル1
入力
3 2 1 3 2 5 5
出力
No Yes 3 6 5 5 1 4 4 2 3 No
$1$ 番目のテストケースについて,条件を満たす整数列 $A, B, C$ は存在しません.例えば,$A = \{1, 2\}, B = \{2, 3\}, C = \{3, 1\}$ とすると,$2$ 番目の条件以外は満たしますが, $A, B, C$ の LIS の長さはそれぞれ $2, 2, 1$ であり,$2$ 番目の条件は満たしません.
$2$ 番目のテストケースについて,整数列 $A = \{3, 6, 5\}, B = \{5, 1, 4\}, C = \{4, 2, 3\}$ は全ての条件を満たします.ほかにも条件を満たす整数列 $A, B, C$ は存在しますが,そのいずれを答えても正解となります.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。