CS Academy: LIS Generator

https://csacademy.com/contest/archive/#task/lis_generator/

問題

100 要素まで使っていいので、最長増加部分列の個数がちょうど K 個であるような数列の一例を示せ。

• 1≦K≦10⁹

解法

二進数で考える。

K=11111 のときは次のように構成すればいい。

K=11101 のときは少しずらす。

K=11001 のときは更にずらす。

適切なずらしを行うことで 00001..11111 のすべてのパターンを作れる。この方法であれば約 90 個で 2³⁰ まで構成できるので OK。

これ出題されてから snackdown で制約緩和版が出されるまで 1 週間経ってないのか…。