問題一覧 > 通常問題

No.3477 Yet Another LIS Triangle

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 32
作問者 : 👑 AngrySadEight / テスター : kidodesu
ProblemId : 13198 / yukicoder contest 494 オムニバス (順位表) / 自分の提出
問題文最終更新日: 2026-03-21 14:01:20
yukicoder contest 494 オムニバスの他の問題:

問題文

整数を三角形状に並べて $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もしくは右上の雲マークをクリックしてアカウントを作成してください。