AtCoder Regular Contest 091 - E LISDL
本番の時は N = A+B or N+1=A+B で考察してWAでした.
問題文
最長増加部分列の長さがA,最長減少部分列の長さがBとなるようなN要素から構成される順列を印刷せよ.
提出
Submission #2751681 - AtCoder Regular Contest 091
解説を殆ど*1見ずにACした.
考察
証明はなし.
初手でNを固定して考察し始めると,なかなか答えが見つからなくなる.
N, Bが与えられず,Aだけが与えられていたとする.N>=Aとする.
この場合,次の手順で最長増加部分列の長さがAとなるような配列が構成出来る.
- A個の配列 を作る.ただし, が成り立つ.
- 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に該当する は
[5,4,3,2,1] [10] [15]
な形で,最大のNに該当する は
[5,4,3,2,1] [10,9,8,7,6] [15,14,13,12,11]
.最小のNと最大のNが分かった.後は最小のNに対応するを構成してから,隙間を埋めるように要素数を増やしていけば良い.
感想
作問した某問題の解法に似ているような気がした*2