けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

LISとLDS

AtCoder ARC 091 E - LISDL (青色, 700 点)

問題へのリンク 問題概要 1, 2, ..., N を並べ替えてできる列であって、以下の条件を満たすものがあるかどうか判定し、あればその例をひとつ構成せよ: 最長増加部分列の長さは A 最長減少部分列の長さは B 制約 1 <= N, A, B <= 3 × 105 解法 LIS and LDS と…

Codeforces #502 (Div. 1 + Div. 2) C. (R1600)

LIS and LDS のバリエーション。 問題へのリンク 問題概要 1〜N の各順列について LIS (最長増加部分列) の長さが A LDS (最長減少部分列) の長さが B とする。A + B を最小化し、A + B が最小となるような順列を具体的に 1 つ求めよ。 制約 1 <= N <= 105 …