KOTET'S PERSONAL BLOG

最近はAtcoderの過去問をのそのそ解いている。 ABC006のD問題の公式の解説がいまいちしっくりこなかったので、 自分の言葉で解説しなおしてみる。 どちらがわかりやすいかは記事を読んだ人によると思う。

問題文

数字が書かれたカードが N 枚あります。このカードの束（山札）に対して以下の操作が可能です。

• 山札からカードを 1 枚抜き取り、任意の場所に挿入する。

山札の上から下に向けて、カードを昇順に並べ替えるために必要な、最小の操作回数を求めてください。

考え方

この操作は、{操作回数}枚のカードを同時に抜いて、それぞれ正しい場所に挿入するのと同じである。

step 0 初期状態

step 1 抜き取る

step 2 挿入する

{操作回数}枚のカードを一度に抜く方法でカードを昇順に並べ替えるには、抜き取ったあと残されたカードが昇順である必要がある。 よって、カードを抜き取ることで作れる最長の昇順列 (この場合 \((1, 3, 5, 6)\) ) の長さを求めて \(N\) (\(=\) カードの枚数) から引けばそれが最小の操作回数になる。 例の場合カードの枚数が\(6\)、最大の昇順列の長さが\(4\)で、最小の操作回数は\(6 - 4 = 2\)である。

最長増加部分列

「カードを抜き取ることで作れる最長の昇順列」のことを最長増加部分列(Longest Increasing Subsequence。以下LISと呼ぶ)と言う。 ある要素\(x\)が昇順列の最後の要素になった時に作れる昇順列の最大の長さ( \(f(x)\) とする)は以下のように求められる。

1. \(x\)が最初の要素なら、\(f(x) = 1\)(列の前にやたら小さい数\(m\)を入れて\(f(m) = 0\)とするとここはなくせる)
2. そうでなければ、\(x\)以前の\(x\)より小さい要素\(p\)のうち、\(f(p)\)が最大のものを探す。その要素を\(q\)とする。
3. \(f(x) = f(q) + 1\)

これを素直に書くと、「自分より前の要素の全探索」を\(N\)回繰り返すので、計算量のオーダーは\(O(n^2)\)になる(このあたり理解が怪しいかもしれない)。 上の例\((1, 3, 5, 2, 4, 6)\)でやってみる。

1. 列を\((m, 1, 3, 5, 2, 4, 6)\)(mは他の要素より小さい数)、
   \(f(m) = 0\)とする。
2. 1番目の要素\(1\)より前の要素で、\(1\)より小さく\(f(p)\)が最大の要素\(p\)は0番目の\(m\)であり、
   \(f(1) = f(m) + 1 = 1\)
3. 2番目の要素\(3\)より前の要素で、\(3\)より小さく\(f(p)\)が最大の要素\(p\)は1番目の\(1\)であり、
   \(f(3) = f(1) + 1 = 2\)
4. 同じように
   \(f(5) = f(3) + 1 = 3\)
5. \(f(2) = f(1) + 1 = 2\)
6. \(f(4) = f(3) + 1 = 3\)
7. \(f(6) = f(5) + 1 = 4\)

これで全要素の「その要素が部分列の最後の要素になった時の最長の長さ」が求まった。 最大値(\(=\)LISの長さ)は\(f(6) = 4\)であり、最小の操作回数は\(N - f(6) = 6 - 4 = 2\)となる。

ここまでの情報で書いたコードが以下のものである。

Submission #1513054 - AtCoder Beginner Contest 006 | AtCoder

最長の実行時間が1792 msとなっており、結構ギリギリ。

高速化

先のやり方では「要素\(x\)が部分列の最後の要素になった時に作れる最長の昇順列の長さ\(f(x)\)」を求めたい要素の前の要素を全探索していた。 ここで、「\(f(c) = length\)となる最小の要素\(c\)」を\(L[length]\)とする。 上の例は

となっているので、最終的な\(L\)は以下のようになる。

以下のようにすると\(f(x)\)が求められる。

1. はじめ\(L[0] = m\) (\(m\)はどの要素よりも小さい)、\(L[l] = M\) (\(0 < l\)、Mはどの要素よりも大きい)とする。
2. 以下の操作が\(x\)の前の要素すべてで行われているものとする。
3. \(L[p] < x\)となる\(p\)のうち最大のものを\(q\)とする。
4. \(L[q + 1] = min(x, L[q + 1])\)
5. \(f(x) = q + 1\)

実際に\((1, 3, 5, 2, 4, 6)\)でやってみる。

1. \(L[0] = m\) (\(m\)はどの要素よりも小さい)、\(L[l] = M\) (\(0 < l\)、 Mはどの要素よりも大きい)
2. はじめの要素\(1\)よりも小さい\(L[p]\)のうち、\(p\)が最大になるのは(\(L[0] = m\))である。
   \(f(1) = 0 + 1\)
   \(L[0 + 1] = min(L[0 + 1], 1) = min(M, 1) = 1\)
   (\(L = (m,1,M,M,M…)\))
3. その次の要素\(3\)よりも小さい\(L[p]\)のうち、\(p\)が最大になるのは(\(L[1] = m\))である。
   \(f(3) = 1 + 1\)
   \(L[1 + 1] = min(L[1 + 1], 3) = min(M, 3) = 3\)
   (\(L = (m,1,3,M,M…)\))
4. 同じように
   \(f(5) = 2 + 1\)
   \(L[2 + 1] = min(L[2 + 1], 5) = min(M, 5) = 5\)
   (\(L = (m,1,3,5,M…)\))
5. \(f(2) = 1 + 1\)
   \(L[1 + 1] = min(L[1 + 1], 2) = min(3, 2) = 2\)
   (\(L = (m,1,2,5,M…)\))
6. \(f(4) = 2 + 1\)
   \(L[2 + 1] = min(L[2 + 1], 4) = min(5, 4) = 4\)
   (\(L = (m,1,2,4,M…)\))
7. \(f(6) = 3 + 1\)
   \(L[3 + 1] = min(L[3 + 1], 6) = min(M, 2) = 2\)
   (\(L = (m,1,2,4,6…)\))

このように全要素の「その要素が部分列の最後の要素になった時の最長の長さ」が求まった。 それら\(f(x)\)のうちの最大値がLISの長さであり、\(N\)からそれを引くと答えになる。

ここで、Lは常に昇順なので、「\(L[p] < x\)となる\(p\)のうち最大のもの」を探すのは二分探索でできる。 そのため、この部分の計算量は\(O(log(n))\)にできる。 それを全要素に対して行うため、全体の計算量は\(O(n log(n))\)となり、はじめより改善されている。

以上をふまえて書いたものがこちら。

Submission #1514573 - AtCoder Beginner Contest 006 | AtCoder

最長の実行時間は10 msとなり、179倍の高速化である。

参考文献

• AtCoder Beginner Contest 006 解説
• 最長増加部分列 | 動的計画法 | Aizu Online Judge
• ALGORITHM NOTE 最長増加部分列 Longest Increasing Subsequence