問題一覧 > 通常問題

No.3477 Yet Another LIS Triangle

レベル : / AI推定難易度 : 1650 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 41
作問者 : 👑 AngrySadEight / テスター : kidodesu
お気に入りにしたユーザー ProblemId : 13198 / 自分の提出
問題文最終更新日: 2026-03-21 14:01:20
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 494 オムニバス (順位表) の他の問題:

Problem Statement

Let's arrange integers in a triangular shape to form $3$ sequences, and make the lengths of the LIS of those sequences all equal to a fixed value.

Determine whether there exist $3$ integer sequences $A, B, C$ satisfying all of the following conditions, and if they exist, show $1$ example.

  • The lengths of $A, B, C$ are all $N$.
  • The lengths of the longest increasing subsequences (LIS) of $A, B, C$ are all $K$.
  • $A_N = B_1$
  • $B_N = C_1$
  • $C_N = A_1$
  • Define the sequence $P$ of length $3N - 3$ as $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}\}$. Then, the sequence $P$ contains each integer between $1$ and $3N - 3$, inclusive, exactly $1$ time.

You are given $T$ test cases; answer each of them.

Constraints

  • $T \geq 1$
  • $2 \leq N \leq 10^5$
  • $1 \leq K \leq N$
  • The sum of $N$ in $1$ input file is at most $10^5$.

Input

The input is given from Standard Input in the following format. Here, $\mathrm{case}_i(1 \leq i \leq T)$ represents the $i$-th test case.

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each case is given in the following format.

$N$ $K$

Output

For each test case, if no integer sequences $A, B, C$ satisfying the conditions exist, print No, followed by a newline. If they exist, print the integer sequences $A, B, C$ in the following format, followed by a newline. If there are multiple integer sequences $A, B, C$ satisfying the conditions, any of them will be accepted.

Yes
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_N$
$C_1$ $C_2$ $\dots$ $C_N$

Sample

Sample 1
Input
3
2 1
3 2
5 5
Output
No
Yes
3 6 5
5 1 4
4 2 3
No

For test case number $1$, no integer sequences $A, B, C$ satisfying the conditions exist. For example, if $A = \{1, 2\}, B = \{2, 3\}, C = \{3, 1\}$, all conditions other than condition number $2$ are satisfied, but the lengths of the LIS of $A, B, C$ are $2, 2, 1$, respectively, so condition number $2$ is not satisfied.

For test case number $2$, the integer sequences $A = \{3, 6, 5\}, B = \{5, 1, 4\}, C = \{4, 2, 3\}$ satisfy all the conditions. There are other integer sequences $A, B, C$ satisfying the conditions, and any of them will be accepted.

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