C - Interval Game

C - Interval Game

Submission #4640210 - AtCoder Grand Contest 025

解法

Aさんの動きは「一番近い区間の端まで移動する」と言い換えられる

すると、左右の振れ幅が大きくなるようにすれば答えは最大に出来る

左が大きい順と、右が小さい順の二つのソート列を用意しておき

同じiを選ばないようにすれば実装できる

Submission #4640210 - AtCoder Grand Contest 025

void solve() {
    cin >> n;
    na2(a, b, n);
    vt rmin, lmax;
    rep(i, n) {
        rmin += mt(a[i], b[i], i);
        lmax += mt(a[i], b[i], i);
    }
    sort(rmin, sifi);
    sort(lmax, fdsd);
    {
        //先に右へ行く
        int cou = 0;
        vi usd(n);
        int li = 0, ri = 0;
        int now = 0;
        rep(i, n) {
            // migi lmax
            if (i % 2 == 0) {
                for (; li < n; li++) {
                    int ind = lmax[li].t;
                    if (usd[ind] == 0) {
                        usd[ind] = 1;
                        brk;
                    }
                }
                int l = lmax[li].f, r = lmax[li].s;
                if (ins(now, l, r+1)) con;
                int cost = min(abs(now - l), abs(now - r));
                cou += cost;
                now = l;
            } else {
                for (; ri < n; ri++) {
                    int ind = rmin[ri].t;
                    if (usd[ind] == 0) {
                        usd[ind] = 1;
                        brk;
                    }
                }
                int l = rmin[ri].f, r = rmin[ri].s;
                if (ins(now, l, r+1)) con;
                int cost = min(abs(now - l), abs(now - r));
                cou += cost;
                now = r;
            }
        }
        cou += abs(now);
        chmax(cou);

    }
    {
        //先にhidaへ行く
        int cou = 0;
        vi usd(n);
        int li = 0, ri = 0;
        int now = 0;
        rep(i, n) {
            // migi lmax
            if (i % 2 == 1) {
                for (; li < n; li++) {
                    int ind = lmax[li].t;
                    if (usd[ind] == 0) {
                        usd[ind] = 1;
                        brk;
                    }
                }
                int l = lmax[li].f, r = lmax[li].s;
                if (ins(now, l, r+1)) con;
                int cost = min(abs(now - l), abs(now - r));
                cou += cost;
                now = l;
            } else {
                for (; ri < n; ri++) {
                    int ind = rmin[ri].t;
                    if (usd[ind] == 0) {
                        usd[ind] = 1;
                        brk;
                    }
                }
                int l = rmin[ri].f, r = rmin[ri].s;
                if (ins(now, l, r+1)) con;
                int cost = min(abs(now - l), abs(now - r));
                cou += cost;
                now = r;
            }
        }
        cou += abs(now);
        chmax(cou);

    }
    cout << ma << endl;
}