このアイデアは JOI ²⁰²¹⁄₂₀₂₂ 春合宿 Day 1 - 京都観光 (Sightseeing in Kyoto) の 解法 が元になっています。

[1] グリッドにする

犬のみを取り出した時 / 猫のみを取り出した時 の順序を固定すると、以下のようなグリッドグラフの左上から右下への最短路になります。

このとき、各マスにおいて、マスの左上から右下に行くときに 右折 / 左折 をするべきかどうか考えます。

例えば、このマスでは、\(3B_1 + 2A_5 < 4A_5 + 5B_1\) なので、このマスで右折するべきではありません。

これを全てのマスに行うと…

右上と左下の範囲に入れなくなります。

[2] 片側について最適化する

\(A\) を前半に入れる要素と後半に入れる要素に分け、\(B\) を前半に入れる要素と後半に入れる要素に分けておくと、

このような形を最適化できればよいです。(\(A, B\) の並び替え方と経路を最適化する)

\(A, B\) の並び替え方は、係数の大きいところに小さい数を入れるべきなので、

• \(A_1 ≥ A_2 ≥ A_3 ≥ \cdots\)
• \(B_1 ≥ B_2 ≥ B_3 ≥ \cdots\)

とするのが最適です。このとき、最短路はどうなるでしょうか？

例えば、\(A_1 > B_1 > A_2 > B_2 > B_3 > A_3\) のとき、各マスについて 右折 / 左折 を考えると…？

右上と左下の範囲に入れなくなります。

つまり、\(A\) と \(B\) をまとめてソートして、大きい順に通れば良いです。

[3] 分配の仕方を最適化する

まとめると、以下のような問題になりました。

\(N, M\) を偶数とする。 (奇数の場合は真ん中を取り除いて全体の重みを \(1\) 小さくすれば偶数の場合に帰着)

1. 空の数列 \(X_1, X_2, Y_1, Y_2\) を用意する。
2. \(A\) と \(B\) をまとめてソートし、大きい順に以下を行う。
   • \(A\) 由来の要素 \(a\) が来たとき、どちらかを選ぶ。
     • \(|X_1| < N / 2\) のとき、\(X_1\) に \(a\) を追加し、コストを \(2a|Y_1|\) 加算する。
     • \(|X_2| < N / 2\) のとき、\(X_2\) に \(a\) を追加し、コストを \(2a|Y_2|\) 加算する。
   • \(B\) 由来の要素 \(b\) が来たとき、どちらかを選ぶ。
     • \(|Y_1| < M / 2\) のとき、\(Y_1\) に \(b\) を追加し、コストを \(2b|X_1|\) 加算する。
     • \(|Y_2| < M / 2\) のとき、\(Y_2\) に \(b\) を追加し、コストを \(2b|X_2|\) 加算する。

これを DP にすれば \(O(NM(N + M))\) で解くことができます。

[4] 大胆予想

以下のようにすることで最小を達成するようです。

• \(A\) 由来の要素 \(a\) が来たとき、\(X_1\) に優先的に入れる。
• \(B\) 由来の要素 \(b\) が来たとき、\(Y_2\) に優先的に入れる。

計算量は \(O(N \log N + M \log M)\) になります。

ストレステストには通りますが、証明はできませんでした。open problem として残しておきます。

追記 : 証明されたようです。