問題：E - LISDL
解答１（通常座圧）：Submission #10767274 - AtCoder Regular Contest 091
解答２（自前計算座圧）：Submission #10767259 - AtCoder Regular Contest 091
解法：次のような2次元マトリクスを考える。
このマトリクスから次のようにN個の数を取得する。
- B, B-1, B-2, ..., 1を取得
- 2B, 2B-1, ... , B+1を取得してゆくが、2Bと3.以降の3B, 4B, ... , ABのBの倍数部分は必ず取得するようにしたい。2B-1以降の数で、その数を取得すると最終的な取得数がN個より多くなる場合は数の取得をやめる。
- 3B, 3B-1, ..., 2B+1についても同様。これをAB, AB-1, ..., (A-1)B+1の列まで繰り返す
このとき取得した数列は長さがN、最長増加列の長さがA、最長減少列の長さがBである。この数列を座標圧縮することで、1からNの数列とすることができる。数の取り方から、A+B-1 ≦ N, AB ≧ Nである場合は必要な数列が取得できることが分かる。
逆に、N, A, Bの設定を満たす数列を取得するためにはA+B-1 ≦ N, AB ≧ Nが必要であることを満たす。
A+B-1 ≦ N については、最長増加列と最長減少列が高々1つの数を共有することから示される。
AB ≧ Nについては、f(i)をi番目の数を増加列の最終項としてもつ増加列の長さの最大値とすると、f(i)の値で数列をグルーピングできる。同じf(i)を持つ数を数列中の順番に並べると、減少列をなす。よって、グループ数は最長の増加列の長さであるA以下、各グループの個数は最長の減少列の長さであるB以下であるため、示される。
