部分点解法

この問題は、\(N\) 個の荷物を \(N\) 個の箱に一つずつ配置する問題なので、割り当て問題とみなすことができます。 よって、各荷物を各箱に移動させるコストを計算することで、ハンガリアン法を用いて \(O(N^3)\) 時間で解くことができます。 コストの総和ではなく、操作回数を優先的に最小化する必要がある点に注意してください。

部分点解法のコード例

満点解法

操作回数を最小とするとき、以下が観察できます。

• すべての荷物について、その移動は「左へ何度か移動する」「右へ何度か移動する」「移動しない」のいずれかである。
• 任意の \(1 \leq i \leq N-1\) について、「箱 \(i\) から箱 \(i+1\) への荷物の移動」と「箱 \(i+1\) から箱 \(i\) への荷物の移動」が両方行われることはない。また、その移動の方向と回数は箱 \(i\) と箱 \(i+1\) の境界の左右に存在する荷物の数の差によって定まる。

操作回数の最小値は、各境界における移動の回数の総和です。 あとは、そのうえでのコストの総和の最小値が求まればよいです。

まず、移動回数が \(0\) の境界があるとき、そこで分割して独立に問題を解くことができます。 したがって、そのような境界は存在しないと仮定します。 このとき、 \(N\) 個の箱は左から順に以下の三つの区間に分割されます。

1. 左に荷物を移動させる箱
2. 中央の \(1\) つの箱（荷物の移動が右にも左にも起こる箱）
3. 右に荷物を移動させる箱

ただし、荷物を左にしか移動しない場合は最も右の箱を、右にしか移動しない場合は最も左の箱を中央の箱と考えます。

中央の箱の中の各荷物について左右の移動可能な方向を決めたとき、すべての箱について移動可能な方向が定まり、その下では貪欲な移動方法が最適となります。 具体的には、荷物の重さが軽い順に「その移動方向について、箱の境界で荷物の移動が起こる残り回数が正である間移動させる」方法が最適となります。 この性質を用いて、以下の \(\mathrm{dp}\) を計算します。

• \(\mathrm{dp}[i][j] \coloneqq {}\) ( \(1, 2, \dots, i\) 番目に軽い荷物を移動できる限り移動させる かつ それらの荷物の中に中央から左に移動したものが \(j\) 個であるときのコストの最小値)

求める答えは、中央から左に移動させる荷物の個数を \(L\) として \(\mathrm{dp}[N][L]\) です。 \(\mathrm{dp}[0][0] = 0\) として、 \(i = 1, 2, \dots, N\) の順に \(\mathrm{dp}[i]\) を計算していきます。 \(i\) 番目に軽い荷物の位置を箱 \(p_i\) 、中央の箱の添字を \(c\) として、 \(p_i\) と \(c\) の大小関係によって場合分けを行います。 ただし、中央の箱からの荷物の移動を無視したうえでの箱 \(i-1\) と箱 \(i\) の間で荷物の移動が起こる残り回数を \(\mathrm{flow}[i]\) とし、動的に管理します。

1. \(p_i < c\)（中央より左にある場合）

この場合は左に移動させることが決まっているので、左に移動させられるだけ移動させるのが最適です。 中央から左に荷物を \(\ell\) 個移動させていたとすると、\(\mathrm{flow}\) の値が \(\ell\) より大きい間は左に移動させることができます。 この位置は \(\ell\) に対して単調増加であることから、各 \(\ell = 0, 1, \dots, L\) について \(O(N+L) = O(N)\) 時間で求まります。 また、\(\mathrm{flow}\) は中央からの荷物の移動を無視するので、 \(\ell=0\) としてできるだけ移動させた場合の残り回数に \(\mathrm{flow}\) を更新します。

2. \(c < p_i\)（中央より右にある場合）

中央の箱からそれまでに移動させた荷物の個数を持っておくことで、左の場合と同様にして求めることができます。 \(\mathrm{flow}\) の更新も同様に行います。

3. \(p_i = c\) の場合

左に移動させる場合と、右に移動させる場合をそれぞれ上二つと同様に行えばよいです。 ただし、中央の箱の荷物なので、\(\mathrm{flow}\) の更新は行いません。

以上の方法により、\(\mathrm{dp}[N][L]\) を \(O(N^2)\) 時間で求めることができます。

クレジット

原案： hamao

解法： tatyam

問題準備・解説： hirakuuuu

レビュー： Jinapetto

テスター： tatyam

校正： nu50218