2019-04-28

AtCoder AGC 032 E - Modulo Pairing (5D, 銅色, 1200 点)

AtCoder AtCoder1200点 AGC-E 二分探索最大値の最小化 Greedy 最適化テク:最適解の形を考える最適化テク：変形しても悪化しない最適化テク:探索候補を絞る数列マッチング Greedyなマッチング区間天才な二分探索銅色diff NoviSteps5D

楽しかった。7 時間かかったけど自力 AC できたー！

問題へのリンク

問題概要

正の整数 $N, M$ が与えられる。 $2N$ 個の $0$ 以上 $M$ 未満の整数 $a_{1}, a_{2}, \dots, a_{2N}$ を $N$ 個ずつのペアに分けたい。

各ペア $(a_i, a_j)$ に対して $(a_i + a_j)$ % $M$ の値 (これを醜さと呼ぶ) を求め、その最大値をとる。

この最大値の最小値を求めよ。

制約

$1 \le N \le 10^{5}$
$1 \le M \le 10^{9}$

考えたこと

一見して、「最大値の最小化」なので、二分探索に思えるけど、最終的にはそういう枠組で二分探索を使うわけじゃないのが面白い。

$N \le 300$ とかだったら、二分探索して、醜さが mid 以下となるペアのみで完全マッチングが作れるかを一般マッチングライブラリで殴る解法が成立する。

今回はそんなことできないので、何かしら Greedy な構造がありそうである。この手の特殊構造をしたマッチングは何かしら Greedy で解けそう感がすごくある。特に今回一般マッチングを求めたいグラフというのは、例えば $M = 7, X = 3$ とすると成立するペアは

0 に対して、0〜3
1 に対して、0〜2 と 6
2 に対して、0〜1 と 5〜6
3 に対して、0 と 4〜6
4 に対して、3〜6
5 に対して、2〜6
6 に対して、1〜6

という風に

左から張り付く区間 [0, p)
右から張り付く区間 [q, M)

みたいな感じになっている。すごく特殊なので、絶対 Greedy な構造があるはず。

最適解に対し、最適性を失わずに解を変形する

こういうときに考えるべきこととして、

最適解が与えられたとして、その最適性を失わずに解をより扱いやすい形に変形できることを示す
その結果、そういう形だけ探索すればよいことがわかる

というテンプレ思考がはまる。これは 400 点難易度から、今回のような中堅難易度まで共通の強力な枠組みである。で、そういう構造を探して実験していくうちに、下図のように四つの値 $a \le b \le c \le d$ について考えたとき、ペアが交差するケースは考えなくてよいことがまず言える。これは実験を繰り返すと予想が立つ。

一応ちゃんと証明すると、

b + d <= M のとき

$a + d \le b + d \le M$ かつ $b + c \le b + d \le M$ より、 $a$ と $d$ 、 $b$ と $c$ をペアにすることで解が悪化することはない。つまり上図の右に寄せられる。

a + c >= M のとき

同様に、 $M \le a + d \le b + d$ かつ $M \le b + c \le b + d$ より、 $a$ と $d$ 、 $b$ と $c$ をペアにすることで解が悪化することはない。

それ以外のとき

$a + b \le a + c$
$c + d - M \lt c \le a + c$

であることから、 $a$ と $c$ のペアは解消して、 $a$ と $b$ 、 $c$ と $d$ をペアにして解が悪化することはないことが言える。つまり上図の左に寄せられる。

以上から、ペアの結びが交差するケースは考えなくて良いことがわかった。

さらに

$a$ と $d$ 、 $b$ と $c$ がマッチングしているとき、片方が $M$ 以上でもう片方が $M$ 未満の場合は、入れ子を解消しても解が悪化しないことが言える。

このことから、最終的に我々は

下図のような「 $M$ 未満のみの入れ子」と「 $M$ 以上の入れ子」に分割することが必ず可能 (入れ子の中で赤青の混在があったらそれを解を悪化させずに変形して分解できる)
その場合のみを考えれば良い

ということが言える。これで切れ目を全探索すればよいので $O(N^{2})$ にはなった。

二分探索で高速化

ここから二分探索が意外とすぐに出てこなかったのが課題。ここまで至ってから 3 時間かかってる。。。

さて、もう少し考えると

「左が青の入れ子」で「右が赤の入れ子」という状況を崩さない限り、切れ目は左にあればあるほど良い
「右が赤」となるような最左の切れ目を考えると、その左側は必ず「青の入れ子」になっている (そうでなければ、分解して赤の入れ子をさらに拡大できるため)

ということに着目する。そうすると

「右が赤の入れ子」となるような切れ目のうち最左のものを二分探索で求める

とすればよいことがわかった。これで完全に解けた。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int N, M;
    while (cin >> N >> M) {
        vector<long long> a(N*2);
        for (int i = 0; i < N*2; ++i) cin >> a[i];
        sort(a.begin(), a.end());

        // [mid, N*2) が大きいものと小さいものをペアにしていったときにすべて >= M となるような最小の mid を求める
        int low = -1, high = N*2;
        while (high - low > 1) {
            int mid = (low + high) / 2;
            long long mi = M;
            for (int i = mid, j = N*2-1; i < j; ++i, --j) chmin(mi, a[i]+a[j]);
            if (mi >= M) high = mid;
            else low = mid;

            //cout << mid << ": " << mi << endl;
        }
        int alt = high/2*2;

        long long res = 1LL<<60;
        for (int num = max(0, alt-10); num <= min(N*2, alt+10); num += 2) {
            long long tmp = 0;
            for (int i = 0, j = num-1; i < j; ++i, --j) chmax(tmp, (a[i]+a[j])%M);
            for (int i = num, j = N*2-1; i < j; ++i, --j) chmax(tmp, (a[i]+a[j])%M);
            chmin(res, tmp);
        }
        cout << res << endl;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます