本番の時は N = A+B or N+1=A+B で考察してWAでした．

問題文

最長増加部分列の長さがA，最長減少部分列の長さがBとなるようなN要素から構成される順列を印刷せよ．

提出

解説を殆ど*1見ずにACした．

証明はなし．

初手でNを固定して考察し始めると，なかなか答えが見つからなくなる．

N, Bが与えられず，Aだけが与えられていたとする．N>=Aとする．

この場合，次の手順で最長増加部分列の長さがAとなるような配列が構成出来る．

例えば．

A = 3の例
制約を満たす3個の配列を作る．各配列の中身は降順ソート済み．
[5,3,1] [8,6] [12,11]
連結すると，
[5,3,1,8,6,12,11]
座標圧縮して，
[3,2,1,5,4,7,6]

各配列の要素数を自由に変化させても最長増加部分列の長さは変わらない．

また，各配列の要素数のうち最大のものが最長減少部分列の長さと一致する．

よって，AとBが与えられた時，最小のNに該当する $w_1,\ldots,w_A$ は

[5,4,3,2,1] [10] [15]

な形で，最大のNに該当する $w_1,\ldots,w_A$ は

[5,4,3,2,1] [10,9,8,7,6] [15,14,13,12,11]

．最小のNと最大のNが分かった．後は最小のNに対応する $w_1,\ldots,w_A$ を構成してから，隙間を埋めるように要素数を増やしていけば良い．

作問した某問題の解法に似ているような気がした*2

*1:コンテスト終了直後に目を通したような通してないような

*2:ネタバレ回避のため，どれとは言わない