No.7 ぬいぐるみの整理 (Plush Toys)


時間制限:$2.0sec$ / メモリ制限:$256MB$

問題文

ある JOI 関係者は,おもちゃ屋で働いている.今日は,店内にあるぬいぐるみコーナーの整理をすることになった.

ぬいぐるみコーナーの棚には,$N$ 個のぬいぐるみが左から右に一列に並べられている.棚は仕切りにより $N$ 個の区画に区切られており,$1$ つの区画に $1$ 個のぬいぐるみを置く.このおもちゃ屋は合計 $M$ 種類のぬいぐるみを売っており,それぞれ $1$ から $M$ までの番号が付けられている.棚に並べられた $N$ 個のぬいぐるみは,それぞれこの $M$ 種類のうちのいずれかである.また,それぞれの種類のぬいぐるみは,少なくとも $1$ 個は存在する.

見栄えを良くするため,同じ種類のぬいぐるみが全て連続して棚に置かれるように,ぬいぐるみを並べ替えたい.次のような方法で,ぬいぐるみを並べ替えることにした.

  • $N$ 個のぬいぐるみのうちいくつかを選び,棚から取り出す.取り出さなかったぬいぐるみの位置は動かさない.
  • 取り出したぬいぐるみを,好きな順に棚の空いている区画に戻していく.

並べ替えた後,同じ種類のぬいぐるみが全て連続して棚に置かれていなければならない. 並べ替えるために取り出すぬいぐるみの個数の最小値を求めるプログラムを作成せよ.

入力

入力は $1 + N$ 行からなる.

1 行目には 2 個の整数 $N, M (1 ≦ N ≦ 100000, 1 ≦ M ≦ 20)$ が空白を区切りとして書かれており,ぬいぐるみが $N$ 個あり,種類が $M$ 種類あることを表す.

続く $N$ 行のそれぞれには,$1$ 以上 $M$ 以下の整数が書かれている. $N$ 行のうちの $i$ 行目 $(1 ≦ i ≦ N)$ に書かれた整数は,棚の左から $i$ 番目の区画に置かれたぬいぐるみの種類を表す.各種類について,少なくとも $1$ 個のぬいぐるみが存在していることが保証される.

出力

並べ替えるために取り出すぬいぐるみの個数の最小値を 1 行で出力せよ.

入出力例

入力1

7 2
1
2
2
2
1
2
1
出力1

2

入力例 1 においては,最初に置かれているぬいぐるみの種類は左から順に $1, 2, 2, 2, 1, 2, 1$ である.並べ替えるために取り出すぬいぐるみの個数を最小にするには,左から $1$ 番目と $6$ 番目のぬいぐるみを取り出し,左から $1$ 番目に種類 $2$ のぬいぐるみを,左から $6$ 番目に種類 $1$ のぬいぐるみを配置すればよい.このとき,取り出すぬいぐるみの個数は $2$ 個である.

入力2

12 4
1
3
2
4
2
1
2
3
1
1
3
4
出力2

7




解説


まず,整理した後のぬいぐるみの配置としてありうるものは,左から並べていく種類の順を決めれば, 左から各種類を詰めていくことで決めることができ,配置の仕方は全部で M! (= 1×2×3×……×M) 通りある. 配置を決めた後,棚から取り出すぬいぐるみの個数を最小にするには,ぬいぐるみを置く場所のうち,最初置かれていた種類と整理した後に置かれる種類が異なる場所のみを取り出せば良い. 並べ方を全通り試し,必要な個数をループで数えると計算量は O(M! × N) となり,MとNがともに小さい場合 (入力 1,2) のみ解くことができる.

配置を決めた後に取り出す必要のある個数を高速に求めるにはどうしたらいいだろうか.これは,累積和を使うことで計算できる.具体的には,まずそれぞれの種類に対して,その種類のぬいぐるみが存在する場所を 1 , 存在しない場所を 0 とした配列を作る.その後,各要素に対し,配列の先頭の要素からその場所までに含まれる値の合計を計算することは,直前の計算結果にさらに値を足すことによって,合計で O(N) で計算できる. この配列を利用すると,連続する区間 [l,r) に含まれる種類 k のぬいぐるみの総数を, sum[k][r]-sum[k][l] のようにして O(1) で求めることができる. この方法を使えば,M の小さいケース (入力 3) を解くことができる.

配置の決め方を全通り試していると M が大きいケースで短時間に答えを求めることができない.そこで,左から見て今までに配置した種類の集合をキーに動的計画法することを考える.(これはビット DP などと呼ばれている方法である) 具体的には, dp[S] := (配置に使った種類の集合が S の時のそこまでで取り出す必要があるぬいぐるみの個数の最小値) とする.集合が S の状態から,さらに 1 種類配置するとき, S に含まれる種類のぬいぐるみの総数だけ左から埋まっている.今まで配置した順にかかわらず,棚のどの位置に次の種類を配置するかがわかるので,次の種類を配置するのに必要な取り出す個数が 累積和の配列を利用すると O(1) で求められる.

この動的計画法を使うと,状態数が O($2^M$) で遷移が O(M) かかるので、動的計画法の部分では計算量は O($2^M M$) となる.これに累積和の計算量を加えても, 全てのケースに正解するのに十分高速であることがわかる.