AGC032-E(Modulo Pairing) 解説 - Mitsubachiのメモ

問題概要

$2N$ 個の整数 $(a_1,a_2,...,a_{2N})$ と $M$ が与えられる。

$2N$ 個の整数を $N$ 個のペアにし、全てのペアに対しその総和を $M$ で割ったときの余りの最大値を最小化したい。最小でいくつにできるか。

$(a_1,a_2,...,a_{2N})$ が $a_1\leq a_2\leq...\leq a_{2N}$ となるようにソートしても当然答えは変わりません。以後は既にソートしてあるものとします。

ステップ1 最大値の最小化といえば

そう、二分探索ですね。答えを $X$ 以下にできるかという判定が $O(N)$ でできるなら、この問題は二分探索で $O(NlogM)$ で解くことができ、これは間に合いそうです。しかし、簡単にはいかなそうです。もし和を $X$ 以下にできるかという問題なら、ある数に対してその数との和が $X$ 以下にできる最大の数を取ればよいです。ただ、今回は $M$ で割った余りを $X$ 以下にできるかという話ですので、合わせるべき数が一意に定まるとは限りません。初手の二分探索は難しそうです。

ステップ2 余りを取らないとする

ステップ1で「和を $X$ 以下にできるかという問題なら、ある数に対してその数との和が $X$ 以下にできる最大の数を取ればよい」と話しましたが、そもそもこの問題( $N$ 個のペアの総和の最大値を最小化したときの値)ならば、 $max(a_1+a_{2N},a_2+a_{2N-1},...,a_N+a_{N+1})$ が答えであるのは感覚的に分かるでしょう。下に証明を書きます。

$N=2$ として、整数 $a_1,a_2,a_3,a_4$ があるとします(ソートしてあるものとします)。この時の答えは $max(a_1+a_4,a_2+a_3)$ であることを示します。 $a_1$ と $a_2,a_3$ と $a_4$ を対応させるとします。その場合の答え $max(a_1+a_2,a_3+a_4)$ は明らかに $a_3+a_4$ ですが、これは $a_1+a_4\leq a_3+a_4,a_2+a_3\leq a_3+a_4$ なのでこのペアは必ずしも最適ではありません。

次に $a_1$ と $a_3,a_2$ と $a_4$ を対応させるとします。その場合の答え $max(a_1+a_3,a_2+a_4)$ は明らかに $a_2+a_4$ ですが、これは $a_1+a_4\leq a_2+a_4,a_2+a_3\leq a_2+a_4$ なのでこのペアも必ずしも最適ではありません。

よって、この問題は $4$ 個の整数がいかなる値でも答えは $max(a_1+a_4,a_2+a_3)$ です。これは $N\geq3$ のときでも適当にペアを作った後、任意に $2$ つのペアを選びこのように組み替えることで答えを最小化していくことができます。これを繰り返すと上の結論( $max(a_1+a_{2N},a_2+a_{2N-1},...,a_N+a_{N+1})$ が答え)が示せます。

この構造を、余りを取る場合にも作れないだろうかと考えてみます。結論から言うと、ある $2$ つのペアを選んだ時にそのペアが共に $M$ 未満もしくは $M$ 以上ならこれが使えます。

ステップ3 $2$ 種類ある場合

つまり選んだ $2$ つのペアが $M$ 未満のペアと $M$ 以上のペア $1$ つずつで構成されている場合です。選んだペア $2$ つに含まれる $4$ つの数を小さい順に $a_1,a_2,a_3,a_4$ とします。

この時、ありえるのは $a_1,a_3$ のペアが $M$ 未満かつ $a_2,a_4$ のペアが $M$ 以上のパターン(これをパターン $1$ とします)、 $a_1,a_4$ のペアが $M$ 未満かつ $a_2,a_3$ のペアが $M$ 以上のパターン(これをパターン $2$ とします)、 $a_2,a_3$ のペアが $M$ 未満かつ $a_1,a_4$ のペアが $M$ 以上のパターン(これをパターン $3$ とします)、 $a_1,a_2$ のペアが $M$ 未満かつ $a_3,a_4$ のペアが $M$ 以上のパターン(これをパターン $4$ とします)のいずれかです

パターン $1$ の場合：

操作前の答えは $a_1+a_3$ です。なぜなら $a_4$ < $M$ より、 $(a_2+a_4)$ % $M$ < $a_2\leq a_3$ < $a_1+a_3$ が示せるからです。

しかし、これをパターン $4$ の形にすると、各ペアの $M$ 未満もしくは以上という関係は変わらないので答えは $a_1+a_2$ もしくは $(a_3+a_4)$ % $M$ < $a_3$ となり、いずれにせよ操作前の答えより増えることはないのは明らかです。

パターン $2$ 、パターン $3$ も同様に示すことができます。(証明は略)

よって、 $2$ つのペアが $M$ 未満のペアと $M$ 以上のペア $1$ つずつで構成されている場合はパターン $4$ のようにするのが最適です。

以上より、 $2$ つのペアを選んだ時に最適となる組み換えの方法が分かりました。これを繰り返すことによって、最適となるペアの組み方の $1$ つに「そこより左は全て $M$ 未満のペア、右は全て $M$ 以上のペアとなる境界を $1$ つ定め、左側右側のペアの組み方は端から順に取っていくことで構成することでできるもの」があることが分かります。