競プロTips勉強メモです。
今日の一問は、トランプ挿入ソート！
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) 2019年8月27日
現代AtCoderでは出づらいストレートな知識勝負。
問題の言い換え→アルゴリズムによる計算量の最適化、という流れは、まさに競プロ的。問題の言い換えまでは頑張ってみよう！#chokudai今日の一問https://t.co/3ZoZKOYLqk
挿入ソートの最悪計算量はです。制約下のカードの最大数
でそのまま挿入ソートを実装するとTLEしそうです。(※)
ここでは昇順になっていないカードを一回で正しい位置に挿入する操作ができるので、逆に配列のなかで既に昇順になっている部分列のうち最長のものの長さを計算することで答えが求まります。
入力例1の135246が与えられた場合は、1346というような部分列の長さを求めればよいことになります。
以下、C#での最長増加部分列(LIS:Longest Increasing Subsequence)の長さを求めるサンプルコードです。
配列の長さをインデックス、長さに対応する部分列の最後の値の最小値をアイテムとする動的計画法での実装です。
このdpテーブルは単調増加なので更新箇所の探索は二分探索で行うことができます。
計算量はになります。
Longest Increasing Subsequence(LIS) with C#
※ 実は解でも通ってしまいます。
