AtCoder AGC 025 C - Interval Game (黄色, 700 点) - けんちょんの競プロ精進記録

コンテスト本番における

僕のコード: https://beta.atcoder.jp/contests/agc025/submissions/2612210
tourist のコード: https://beta.atcoder.jp/contests/agc025/submissions/2609185

解けたとはいえ、反省点も多い感じですね。。。

問題へのリンク

問題概要

N 個の区間 [L_i, R_i] が与えられる。区間の順序 (N! 通りある) を 1 つ決めたときの得点を

高橋君が地点 0 から出発する
各 i に対して順に i 番目の区間に対して、高橋君が今いる地点から見て最小距離の移動で区間内に収まる地点へと移動する (今いる地点が既に区間内に収まっている場合は移動なし)
最後に地点 0 へと最短距離で移動する

を行ったときの総移動距離とする。順序を工夫したときの総移動距離の最大値を求めよ。

制約

1 ≦ N ≦ 10⁵
−10⁵ ≦ L_i < R_i ≦ 10⁵

解法

(注意: 上の問題概要は既に「高橋君の最適戦略」を反映しています)

基本的なアイディアとしては、高橋君を左右に振るとよいです。高橋君は、区間が与えられた時の移動は以下のいずれかになります

既に区間に含まれているため動かない
高橋君が与えられた区間の左側にいるため、与えられた区間の左端に移動する
高橋君が与えられた区間の右側にいるため、与えられた区間の右端に移動する

「動かない」の扱いがちょっとイヤなのですが、とりあえず一旦は無視して考えると、

区間のうちいくつかを、高橋君を左端へと移動させるものへと割り当てる
区間のうちいくつかを、高橋君を右端へと移動させるものへと割り当てる

ということを考えることになります。そして、1 と 2 の回数差が 1 以下であって (1 と 2 を交互に繰り出して高橋君を左右に振らせる)、かつ、1 と 2 との逆転 (1 の区間の左端よりも、2 の区間の右端の方が右側にある現象) が起きない限りは、

(左端へと割り当てられた区間の左端の値の合計 - 右端へと割り当てられた区間の右端の値の合計) * 2

が総移動距離となります。左端が負だったり右端が正だったりしてもこれは成り立っています。従って基本的方針としては

左端が大きい順に「左端へと移動させる」へ Greedy に割り当てる
右端が小さい順に「右端へと移動させる」へ Greedy に割り当てる

を交互に繰り返すようにして行きます (左端と右端が同数の場合はどちらから始めてもよく、左端の方が 1 個多いときは左端スタート、右端の方が 1 個多いときは右端スタート)。上記の「左端と右端の逆転現象」が起きない限り、同一の区間が「左端側」「右端側」の両方に割り当てられるようなことは起こらないことに注意です。

さて、ここまで考えて気になるのは

「動かない」区間の扱い
「左端と右端の逆転現象」の扱い

ですが、ここで最適化問題に取り組む上での常套手段を繰り出します。

最適順序があったときに、不要区間を取り除いたりすることで、その最適性を変えずに、高橋君が区間の左端と右端とを反復横跳びするケースに変形できる

つまりは、

動かない
左端と右端が逆転しているがために高橋君が 2 回連続で同じ方向への移動を余儀なくされる

ケースは考えなくてもよいということになります。あとは上記の Greedy を実装すればよいです。tourist のコードはいくらなんでも鮮やかすぎて書けそうにないので、下の感じで妥協してみました。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<long long> left(N), right(N);
    for (int i = 0; i < N; ++i) cin >> left[i] >> right[i];
    sort(left.begin(), left.end(), greater<long long>());
    sort(right.begin(), right.end());
    long long res = 0, tmp = 0;

    // left スタート
    tmp = 0;
    for (int i = 0; i < N; ++i) {
        tmp += left[i]; res = max(res, tmp);
        tmp -= right[i]; res = max(res, tmp);
    }

    // right スタート
    tmp = 0;
    for (int i = 0; i < N; ++i) {
        tmp -= right[i]; res = max(res, tmp);
        tmp += left[i]; res = max(res, tmp);
    }

    cout << res * 2 << endl;
}