AtCoder Grand Contest 028: C - Min Cost Cycle

https://atcoder.jp/contests/agc028/tasks/agc028_c

問題概要

N頂点の有向グラフがあり、各頂点iは2つの値Ai, Biを持っている。このグラフはすべての点対x, yに対して辺x->yが存在し、その重みはmin(Ax, By)である。グラフのすべての頂点をちょうど1回ずつ通るような有向サイクルのうち、含まれる辺の重みの和が最小となるときの値を求めよ。

N <= 105

解法

サイクルを作ったとき、ある辺x->yのコストはAxもしくはByである。言い換えると各辺はAかBのどちらかに塗り分けられることになる。なので各頂点は「出る辺がAかBか」「入る辺がAかBか」で4パターンに分類することができる。このことからある頂点iを以下の4パターンに分類できる。

  1. 出る辺がAで入る辺がA: Aiは最終的なコストに含まれるが、Biは最終的なコストに含まれない。
  2. 出る辺がAで入る辺がB: AiもBiも最終的なコストに含まれる。
  3. 出る辺がBで入る辺がA: AiもBiも最終的なコストに含まれない。
  4. 出る辺がBで入る辺がB: Aiは最終的なコストに含まれないが、Biは最終的なコストに含まれる。

実は各Ai, Biを一緒くたにソートした上で小さい値から都合よく貪欲に取っていっても、上の塗り分けを適切にやればほとんどの場合そのような頂点の配置を実現できる。

唯一実現できないのが「すべての頂点からちょうど1つずつAかBを取っている」かつ「AとBのどちらも少なくとも1つ以上取っている」場合である。「すべての頂点からちょうど1つずつAかBを取っている」ということは、上でいうパターン2, パターン3の頂点が存在しないということである。ということはサイクルにおいてその頂点を境にA, Bが切り替わるような頂点が存在しないことになる。つまりサイクルの辺はすべてAもしくはすべてBのどちらかしかありえない。しかしこれは「AとBどちらも少なくとも1つ以上取っている」に矛盾する。よってこのようなとり方は不可能である、ということになる。

そのため最終的な解としては、まずAiとBiを全部並べてソートする(ただし値の頂点番号とA, Bの分類は覚えておく)。次に小さい方から貪欲にN個取る。もしこれが上の実現不可能パターンに当てはまらなければこの合計をそのまま答えとする。もし当てはまっているのであれば、そのままでは駄目なので辻褄をあわせる必要がある。単純に考えるとN番目と(N+1)番目を入れ替えればよさそうだが、このときこれらの頂点番号が一緒だと入れ替えても実現不可能パターンから外れない。なのでその場合にはN番目と(N+2)番目の入れ替えと(N-1)番目と(N+1)番目の入れ替えを試して小さい方を取るようにする。

計算量はソートの部分が一番重くてO(NlogN).

感想

わからなかった. 下界が簡単にわかる -> 実際にそれが(ほとんどの場合)達成できる という問題だと思えば結構類型的なのかな

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.string;

void main() {
    auto N = readln.chomp.to!int;
    auto AB = N.iota.map!(_ => readln.split.map!(to!long).array).array;

    Tuple!(long, int, int)[] C;

    foreach (i; 0..N) {
        foreach (j; 0..2) {
            C ~= tuple(AB[i][j], i, j);
        }
    }
    C.sort!"a[0] < b[0]";

    long ans = 0;
    auto cnt1 = new int[](N);
    auto cnt2 = new int[](2);

    foreach (i; 0..N) {
        ans += C[i][0];
        cnt1[C[i][1]] += 1;
        cnt2[C[i][2]] += 1;
    }

    if (cnt1.map!(c => c == 1).all && cnt2[0] != 0 && cnt2[1] != 0) {
        if (C[N-1][1] == C[N][1]) {
            ans = min(ans - C[N-2][0] + C[N][0], ans - C[N-1][0] + C[N+1][0]);
        } else {
            ans = ans - C[N-1][0] + C[N][0];
        }
    }

    ans.writeln;
}