pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

CS Academy: LIS Generator

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

問題

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

  • 1≦K≦109

解法

二進数で考える。

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

f:id:pekempey:20160606183614p:plain

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

f:id:pekempey:20160606183619p:plain

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

f:id:pekempey:20160606183623p:plain

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

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