ARC145 C - Split and Maximize 解法の正当性

ARC145 C - Split and Maximize の公式解説があっさりしていて説明不足だと思ったので、行間を埋めていたら結構たいへんだった。

スコアが最大となる構造の分析

$A\lt B\lt C\lt D$ のとき、 $AD+BC\lt AC+BD\lt AB+CD$ が成り立つのは公式解説の通りです。
$1$ 〜 $2N$ を使った $N$ ペアの作り方が任意に与えられたとします。ペア $\{1,X\}$ と $\{2,Y\}$ があるとき、 $\{1, 2\}$ と $\{X, Y\}$ にペアを組み替えます。するとスコアを減少させずに $\{1,2\}$ のペアが作れます。続けて $3$ と $4$ 、 $5$ と $6$ 、 $\cdots$ 、 $2N-1$ と $2N$ に注目して同じことを繰り返すと、スコアを減少させずに $\{1, 2\}, \{3, 4\}, \dots, \{2N-1, 2N\}$ というペアに組み替えることができます。任意のペアの作り方についてこれが言えるので、 $\{1, 2\}, \{3, 4\}, \dots, \{2N-1, 2N\}$ というペアを作ったときが最大スコアとなります。

括弧列との対応付け

ここが説明不足だと感じました。
スコア $M$ を達成する順列 $P$ をとります。そして、そのスコア $M$ を達成する $A,B$ の分割をひとつとります。 $P$ の先頭から $A$ に振り分けられたものを ( と書き、 $B$ に振り分けられたものを ) と書いて並べることで、ひとつの括弧列を得ます。ここで、この括弧列はバランスがとれているとは限らないことに注意してください。
この括弧列を先頭から見ていって、初めてバランスが壊れる)の場所を見つけ、それ以降の(と)を反転させます。これは $A$ に振り分けものと $B$ に振り分けるものを交換することを意味し、操作後も分割のスコアは $M$ のままです。この操作を括弧列のバランスがとれるまで繰り返すことで、スコア $M$ を達成する $A,B$ の分割であって、対応する括弧列のバランスがとれているものが得られます。
つまり、スコア $M$ の順列があったとき、スコア $M$ を達成し、対応する括弧列がバランスのとれているような分割がただひとつ存在します。よって、バランスのとれた括弧列すべてに対して、対応する分割のスコアが $M$ になるような順列を数え上げればよく、あとは公式解説の通りです。

感想

解法を考えるより、解法の正当性を示すほうが楽しい（ときもある）。