tatyam によるユーザ解説 (https://atcoder.jp/contests/abc290/editorial/5800) で提示された予想の証明を行います。なお、tatyam によるユーザー解説の前半部分は公式解説と同じ結果を異なる手法で示しているもので、予想の主張や証明の理解には必ずしも必要ではありません。

公式解説により以下の事実が示されています。

• \(N, M\) がいずれも偶数の場合のみ解ければ十分である。
• 列を左右で半分に分けたとき、犬がそれぞれに \(N / 2\) 匹ずつ、猫がそれぞれに \(M / 2\) 匹ずつ入っており、さらに左半分は不満度が昇順、右半分は不満係数が降順になっている最適解が存在する。

猫と犬を不満係数の降順に見ていき、中央に詰めていく過程を考えます。 すると結局、以下の問題を解くことになります。

長さ \(2n + 2m\) の広義単調減少な非負整数列 \(S\) がある。 \(S\) の要素のうち \(2n\) 個には \(A\) のラベルが、残りの \(2m\) 個には \(B\) のラベルが付いている。 変数 \(X_1, X_2, Y_1, Y_2\) を最初全て \(0\) とする。 \(s = S_1, S_2, \dots, S_{2n+2m}\) の順に以下の操作を行う。 コストを最小化せよ。

• \(s\) のラベルが \(A\) のとき、どちらかを選ぶ。
  1. \(X_1\) に \(1\) を足し、\(s Y_1\) のコストを加算する。
  2. \(X_2\) に \(1\) を足し、\(s Y_2\) のコストを加算する。
• \(s\) のラベルが \(B\) のとき、どちらかを選ぶ。
  1. \(Y_1\) に \(1\) を足し、\(s X_1\) のコストを加算する。
  2. \(Y_2\) に \(1\) を足し、\(s X_2\) のコストを加算する。

ただし、この過程で \(X_1\) と \(X_2\) は \(n\) 以下、\(Y_1\) と \(Y_2\) は \(m\) 以下である必要がある。

予想 (tatyam): ラベルが \(A\) のときは選択肢 \(1\) を、ラベルが \(B\) のときは選択肢 \(2\) を優先的に選ぶことで得られる操作列を \(\bigstar\) と呼ぶことにする。操作列 \(\bigstar\) は最適解 (の \(1\) つ) である。

任意の広義単調減少な非負整数列は、値が \(\{0, 1\}\) の広義単調減少な列の和で表せることに着目します。 コストも \(s\) に対して線形なので、\(S\) が \(0, 1\) のみからなる場合について最適性を証明できれば十分です。 例えば、\(S = (5_A, 5_B, 3_B, 2_A)\) を考えてみます。 \(S_p = (1_A, 1_A, 0_B, 0_A), S_q = (1_A, 1_B, 1_B, 0_A), S_r = (1_A, 1_B, 1_B, 1_A)\) とすると、\(S_p, S_q, S_r\) の全てについて操作列 \(\bigstar\) は同じ操作列です。 したがってこれらについて \(\bigstar\) が最適ならば、\(S = 2 S_p + 1 S_q + 2 S_r\) についても \(\bigstar\) が最適であることが言えます。

補題: \(S\) が \(0, 1\) のみから成るならば、\(\bigstar\) は最適である。

\(S\) に含まれる \(1\) のうち、\(A\) のラベルがついたものを \(x\) 個、\(B\) のラベルがついたものを \(y\) 個とします。 \(S\) の並び方によって \(\bigstar\) は異なる操作列になりますが、実はそのコストは常に

\[ \begin{cases} 0 & \quad (x \leq n, y \leq m) \\ x(y-m) & \quad (x \leq n, y \geq m) \\ y(x-n) & \quad (x \geq n, y \leq m) \\ m(x-n)+n(y-m) & \quad (x \geq n, y \geq m) \end{cases} \]

と一致します。 これは \(x + y\) に対する数学的帰納法を用いて、\(S\) に出現する最後の \(1\) とそれ以外の \(1\) でそれぞれに掛かるコストを考えると示すことができます。

ところで、広義単調減少性を保ったまま \(S\) を並び替えても最適なコストは変化しません。 これは公式解説の議論を追っても良いですし、言い換える前の問題において不満係数に十分小さい値を足し引きして順序を操作したと思っても良いです。 \(S\) においてラベルが \(A\) であるような \(1\) がもっとも手前に並ぶように並び替えると、\(\bigstar\) が最適であることは明らかです。 よって \(S\) がどのように並んでいたとしても前述したコストが最適値であり、\(\bigstar\) は最適な操作列です。\(\blacksquare\)