7K12 blog

猫でも分かるアルゴリズム解説

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

f:id:tkr987:20200801001610p:plain

https://atcoder.jp/contests/abc006/submissions/15555175

  • ソートするためには最低でも最長増加部分列(LIS)以外は移動する必要がある

f:id:tkr987:20200801004339p:plain
マージソートなどは木構造を使って1枚あたりの計算量を O(\log N)に減らすが、これは計算量を求める問題ではない。どんなソートを使っても最長増加部分列以外のカードを動かさないと永遠にソートされないため N - Size(LIS) が答えになる。