公式解説の以下の部分に対して補足します。

実際、もし \((1,1)\) 型のある \(2\) 要素 \(A_i,A_j\) が、 \(C_i<C_j\) であるにもかかわらず、 \(A_i\) は (B) を選択し、 \(A_j\) は (A) を選択していた場合、 \(A_i\) と \(A_j\) の役割を交換することで、合計費用をより小さくすることができます。

費用の計算の際に \(C\) をソートするという複雑な工程が入っており、そのことに束縛されてしまうと上記の事実を示すことが困難になります。どのように証明すれば良いでしょうか？

まず、 \(A_i\) で (B) を選択し \(A_j\) で (A) を選択した場合の最適な操作列を \(S\) とします。
この時点で、操作列 \(S\) での \(A_i\) と \(A_j\) の役割を交換します。すなわち、操作列 \(S\) 中で \(A_i\) を \(1 \rightarrow 0\) に変更する際に代わりに \(A_j\) に対してそのような操作を行うものとします。 \(0 \rightarrow 1\) に変更する際も同様です。こうして得られた列を \(S'\) とします。

ここで、 \(S\) から \(S'\) に変更した際に総コストがどのように変動するか調べます。

• \(S\) について、 \(C_i\) が総コストに \(x\) 回、 \(C_j\) が総コストに \(|S|\) 回寄与するものとする。
  • ここで、 \(1 \rightarrow 0\) の際は \(C_i\) は総コストに寄与しないので、 \(x < |S|\) が成り立ちます。
• すると、 \(S'\) について、 \(C_i\) が総コストに \(|S'|\) 回、 \(C_j\) が総コストに \(x\) 回寄与する。
  • 列の構成法より、 \(|S| = |S'|\) です。
• \(C_k (k \neq i,j)\) について、総コストに寄与する回数は不変である。

\(C_i < C_j\) であることから、 \(S\) から \(S'\) に変更した際に総コストは減少することがわかります。

さらに、 \(S'\) は改善の余地があります。というのも、 \(S'\) は公式解説中 (★) の条件を満たしているとは限らず、そこから (★) の条件を満たすように変更することで総コストは元のコスト以下になります。

まとめると、「 \(S\) 中の操作の対象として \(A_i\) の代わりに \(A_j\) を取った \(S'\) にするだけで総コストが改善するのに、更に \(S'\) にだけ総コスト改善の余地があるので、わざわざ冒頭のような選択をする必要はない」ということが分かります。