332.1

SRM

昨日の続き。

950

1からNまでの数字を、部分列のうち最長の単調増加列の長さをMに、最長の単調減少列の長さをKになるようにならびかえて、辞書順で先頭のものを答えよ、という問題。


先頭のいくつかを昇順に並べて、残りが実現可能かを吟味する。実現可能かどうかは、次のK個降順に並べるのをNまで繰り返したときに、この繰り返しが前に並べた数とあわせてM以下であること。(Mよりも十分に小さい時には、K個降順に並べないで済むので、より多く昇順に並べることができる。)