C - Min Cost Cycle

C - Min Cost Cycle

解法

n個を並べて、辺のコストをaかbとしていい

この時iについてabの選び方は以下の4通りある

これらを輪にできるようなabの取り方は実現できる

全てa,全てbのような取り方は出来ることがわかる

abを取り入れるとどうなるだろうか

あるaをabに変えると、aが一つ_に変わることが分かった

また、abと_の間にはbを好きなだけ並べられ、_とabの間にはaを好きなだけ並べられることがわかる（ここでabは二つあるわけではなく、一周している）

上を言い換えると、あるiについてaiとbiを取った時、それ以外の2n-2個のa,bから好きにn-2個を選べるという事になる。

ここで、abを2つ以上持つメリットはない。

よって答えは 「aをすべて選ぶ」、「bをすべて選ぶ」、「aiとbiを取り、それ以外からn-2個選ぶ」のどれか

Submission #4662777 - AtCoder Grand Contest 028

void solve() {
    cin >> n;
    na2(a, b, n);
    vt c;
    vi ai(n), bi(n);
    rep(i, n) {
        c += mt(a[i], i, 0);
        c += mt(b[i], i, 1);
    }
    sort(c);
    rep(i, n * 2) {
        if (c[i].t == 0) {
            ai[c[i].s] = i;
        } else {
            bi[c[i].s] = i;
        }
    }

    //all a
    chmi(sum(a));
    //all b
    chmi(sum(b));

    vi d;
    rep(i, n * 2)d += c[i].f;
    au rd = ruic(d);

    //iのabをつかう
    rep(i, n) {
        int r = n - 2;
        int sum = 0;
        if (ai[i] > bi[i]) {
            swap(ai[i], bi[i]);
            swap(a[i], b[i]);
        }
        if (ai[i] < r)r++, sum -= a[i];
        if (bi[i] < r)r++, sum -= b[i];
        sum += rd[r] + a[i] + b[i];
        chmi(sum);
    }
    cout << mi << endl;
}