【JOI2016】D - ぬいぐるみの整理 (Plush Toys)
公式の解説
参考にした解説
上の解説を自分なりに咀嚼してみました。
$O(M!)$の解法
ぬいぐるみの初期配置が「1232132」の場合で考えてみます。
まずは計算量が$O(M!)$の解法について考えます。
左から順番に連続するぬいぐるみの種類の詰め方を列挙します。
今は3種類のぬいぐるみが存在するので、「123, 132, 213, 231, 312, 321」の6(=3!)通り存在します。
例えば「123」の詰め方の場合、並び替えた後の配置は「1122233」となります。
他にも「312」の場合は「3311222」となります。
ここから入れ替えるぬいぐるみの個数を数えていきます。
下の表を作ります。
| 場所1 | 場所2 | 場所3 | 場所4 | 場所5 | 場所6 | 場所7 | |
|---|---|---|---|---|---|---|---|
| 元の配置 | 1 | 2 | 3 | 2 | 1 | 3 | 2 |
| 123の配置 | 1 | 1 | 2 | 2 | 2 | 3 | 3 |
| 一致 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
「元の配置」が最初に絵耐えられた配置。
「123」の配置が左から順番に連続する種類を決めたときの配置。
「一致」は「元の配置」と「123」の配置で数字が同じなら1, 違う場合は0。
「一致」の中の0の個数が場所を入れ替えるぬいぐるみの個数になります。
上の例では4個になります。
これを全ての「123, 132, 213, 231, 312, 321」について調べて最も個数の少ない配置が答えになります。
ただ、問題の制約で種類$M $が$M\le 20$なので$M!$がものすごく大きな数になり間に合いません。
$O(2^{M})$の解法
次に計算量が$O(2^{M})$の解法について考えます。
動的計画法(DP)を使います。
種類Mの部分集合をSとして、DPテーブルを以下のように定義します。
- DP[S] := Sに含まれる種類のぬいぐるみを左から順番に詰めるまでに必要な入れ替え数。
例えばS={1,2}の場合は左から順番に12(あるいは21)と連続して同じ種類のぬいぐるみを配置した時に必要な入れ替え数になります。
Sはあくまでも左に詰めることが決まった種類の組み合わせだけを表しており、実際の順番は分からない。
上の例では順番としては「12」か「21」が考えられますがどちらになったかは分かりません。
これを知ろうとすると結局$O(M!)$と同じ計算量が必要になります。
あくまでも左から連続することが確定した集合にしか過ぎません。
なので計算量を$O(2^{M})$まで落とすことが出来ます。
次にSに含まれていない種類iを新たにSに加えてDPを更新していきます。
更新にはiを加えたときに必要な入れ替え個数を数える必要があります。
それが計算できたとしてその数がx[i]とすると更新式は以下のようになります。
- DP[S U i] = min(DP[S U i], DP[S]+x[i])
「S U i」は集合Sに新しい要素iを加えた集合を表します。
では最後にx[i]の計算方法について考えていきましょう。
これを計算するには種類毎の累積和が必要になります。
種類毎に配列accumを準備してある位置iまでに登場した種類の累積和を管理します。
accum[m][i]は場所iまでに存在する種類mのぬいぐるみの累積和を表します。
またaccum[m][0]=0と定義します。
| 場所1 | 場所2 | 場所3 | 場所4 | 場所5 | 場所6 | 場所7 | |
|---|---|---|---|---|---|---|---|
| 元の配置 | 1 | 2 | 3 | 2 | 1 | 3 | 2 |
| 1の累積和 | 1 | 1 | 1 | 1 | 2 | 2 | 2 |
| 2の累積和 | 0 | 1 | 1 | 2 | 2 | 2 | 3 |
| 3の累積和 | 0 | 0 | 1 | 1 | 1 | 2 | 2 |
場所rからlまでに含まれる種類mのぬいぐるみの数はaccum[m][r] - accum[m][l]で計算できます。
(r-l == accum[m][r] - accum[m][l]ならその区間は同じ種類のぬいぐるみが連続しているとも言える。)
例えばm=2のr=6からl=2に含まれる同じ種類のぬいぐるみの数はaccum[m][r] - accum[m][l]=3-1=2になります。
実際に場所3と場所6に種類2のぬいぐるみが存在しています。
ある位置tまで既に連続する種類で整理されておりそこからLだけ別の種類mのぬいぐるみを連続して配置したい場合を考えます。
cnt[m]が種類mのぬいぐるみの総数と定義すると、tは今までに調べた部分集合Sに含まれる種類についてcntの和を取れば計算できます。($t=\sum_{i\in S}cnt[i]$)
次にこのxからx+Lの区間に既に配置されている種類mのぬいぐるみの個数を調べます。
これはaccum[m][x+L]-accum[m][L]から計算できます。
既に種類mのぬいぐるみが配置されていれば入れ替える必要はないためx[m]は以下のように計算できます。
- x[m] = cnt[m] - (accum[m][x+L]-accum[m][L])
以上で解法が整備できました。
実際に上の例で計算してみましょう。
DP[0] = 0、それ以外はINFで初期化しておきます。
S = {1}の場合について計算してみます。
種類1のぬいぐるみの個数は2個なのでcnt[1]=2になります。
場所2までを種類1のぬいぐるみで連続させるときに必要な入れ替え数について考えます。
これはcnt[1] - (accum[1][2]-accum[1][0]) = 2 - (1 - 0) = 1になります。
| 場所1 | 場所2 | 場所3 | 場所4 | 場所5 | 場所6 | 場所7 | |
|---|---|---|---|---|---|---|---|
| 元の配置 | 1 | 2 | 3 | 2 | 1 | 3 | 2 |
| 確定した配置 | 1 | 1 |
ここでDP[{1}] = 1に更新されます。
次に種類2を加える場合について考えます。
cnt[2] = 3です。始まりの位置はt=cnt[1]=2になります。
これより場所2から場所5までに存在する2の数を計算して見ます。
accum[2][5]-accum[2][2] = 2 - 1 = 1になります。
よって種類2について入れ替える個数はcnt[2] - (accum[2][5]-accum[2][2]) = 3-1 = 2になります。
これよりDP[{1, 2}] = DP[{1}] + 2 = 3に更新されます。
| 場所1 | 場所2 | 場所3 | 場所4 | 場所5 | 場所6 | 場所7 | |
|---|---|---|---|---|---|---|---|
| 元の配置 | 1 | 2 | 3 | 2 | 1 | 3 | 2 |
| 確定した配置 | 1 | 1 | 2 | 2 | 2 |
最後に種類3を加える場合について考えます。
cnt[3]=2です。始まりの位置はt=cnt[1]+cnt[2]=2+3=5になります。
これより場所5から場所7までに存在する3の数を計算して見ます。
accum[3][7]-accum[3][5] = 2 - 1 = 1になります。
よって種類3について入れ替える個数はcnt[3] - (accum[3][7]-accum[3][5]) = 2-1 = 1になります。
これよりDP[{1, 2, 3}] = DP[{1, 2}] + 1 = 3+1=4に更新されます。
この結果は$O(M!)$の例で計算した結果と一致しています。
以上をS={0}, {1}, {2}, {3}, {1,2}, {2, 3}, {3, 1}, {1,2,3}それぞれについて更新していきS={1,2,3}となった時のコストの最小値を求めれば良いです。
$O(M!)$の時は3つの数字の並びについて全列挙していました。
(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)の6通り。
今回は$2^{M}$通りの部分集合(冪集合)に対して状態を遷移させていき最終的には1種類のS={1,2,3}に到達した時の個数の最小値を求めています。
((1,2,3)なのか(3,2,1)なのかは区別していない。)
$M=3$では$2^{M}$の方が計算量は大きくなりますがさらに$M$が大きい場合は$2^{M}$の方が計算量は減ります。
$M=20$では$2^{M}=1048576$なのに対して$20!=10^{18}$になってしまいます。
C++で実装したコードを以下ににUpしました。
