競技プログラミングにおける最長部分増加列問題まとめ

最長部分増加列

• LIS : Longest Increasing Subsequense
• 参考サイト
• 入れ子構造がLISに帰着できるケースはよくある(この問題は違うけど)
• 二次元での入れ子構造は二次元平面上にプロットすると考えやすい 例1 例2
• 一般に単調増加は狭義単調増加であるが、広義単調増加として解く問題もある

問題

• 普通のLIS
  • AOJ 最長部分増加列
  • ABC006 D. トランプ挿入ソート
  • AGC024 Backfront 解説
  • ABC038 D. プレゼント
  • AGC019 Fountain Walk 解説
  • Typical DP Contest K. ターゲット
  • Codeforces #277 E. LIS of Sequence
  • Codeforces #345 Div1. D. Zip-line
  • 「みんなのプロコン」 決勝 D. KthLIS
  • CSAcademy Critical Cells
  • JOI春合宿2016 A. マトリョーシカ人形
  • yukicoder No.711 競技レーティング単調増加
  • ARC101 Robots and Exits （二次元）
  • EDPC Flowers 解説
  • AOJ LISum 解説
• 3次元LIS
  • AOJ Longest Chain 解説1 解説2
  • SRM747 Div1 Hard RochesterSequence https://www.hamayanhamayan.com/entry/2019/01/20/145544title=解説

以下、解説への手引き

解説への手引き

AOJ 最長部分増加列

基本

ABC006 D. トランプ挿入ソート

LISやるだけだけど、気づくまでが問題

Codeforces #277 E. LIS of Sequence

LISをして、そっから色々やる
kmjpさんの解説

Codeforces #345 Div1. D. Zip-line

LISをして、そっから色々やる
kmjpさんの解説

「みんなのプロコン」 決勝 D. KthLIS

LISをして、そっから色々する
kmjpさんの解説

ABC038 D. プレゼント

入れ子構造系LIS

Typical DP Contest K. ターゲット

入れ子構造系LIS
kmjpさんの解説

CSAcademy Critical Cells

入れ子構造っぽいLIS
広義単調増加列のLIS

JOI春合宿2016 A. マトリョーシカ人形

入れ子構造ではあるが、難しい
神解説