第一回日本最強プログラマー学生選手権-予選- E - Card Collector

いい加減マトロイドの基本をスラスラと思い出せるようにならないと非常にまずいと感じた。
E - Card Collector

問題

H 行 W 列のマス目の上に N 枚のカードが置かれている。i番目のカードは R[i] 行 C[i] 列に置かれており、整数 A[i] が書かれている。(同じマス目に2枚以上のカードが置かれる可能性もある。)
以下のようにカードを取るとき、取ったカードに書かれている整数の合計値としてありうるものの最大値を求めよ。

  • 各行から最大1枚取る。
  • その後、各列から最大1枚取る。その際、直前のステップで取ったカードは取れない。

解法

「マトロイドの上の貪欲法」の一言で片付けられるが、片付けずマトロイドについての定理をこの問題での場合に特殊化して記述する。

M をカード全体の集合とする。カードの集合 A に含まれるカードを全部取れるとき、集合 A を独立集合と呼ぶことにし、集合族 F を F := {A \subseteq M | 集合 A は独立集合} で定める。
以下の補題を示す。

(補題: 増加公理) 独立集合 A, B に対して、|A| > |B| が成り立つ場合、ある x \in A \setminus B が存在して B \cup \{x\} は独立集合。

(証明)*1
A = A0 \coprod A1, B = B0 \coprod B1 とし、A0, B0 は行ごとに最大1個、A1, B1 は列ごとに最大1個のカードが含まれるような集合とする。 |A| > |B| であるため、|A0| > |B0| か |A1| > |B1| のどちらかは成立する。一般性を失わず、|A0| > |B0| として良い。
A0 でカバーされていて B0 でカバーされていない行が存在するので、ある x \in A0 \setminus B0 が存在して、 B0 \cup \{x\} は行ごとに最大1個のカードしか含まない。

  1. そのような x であって、B1 に含まれないものが存在する場合
    x は B に含まれず (B0 \cup \{x\}) \coprod B1 は独立集合である。
  2. そのような x がすべて B1 に含まれる場合
    そのような要素を B1 側から B0 側に持ってくることで、 B = A0 \coprod (B1 \setminus (A0 \setminus B0)) とできる。 C := B1 \setminus (A0 \setminus B0) と置くと |A1| > |C| であるため、列に対して同じ議論を行うことで、ある y \in A1 \setminus C が存在して B \cup \{y\} は独立集合であることがわかる。(終)

増加公理を利用して、以下の貪欲を行う。

  1. 集合 S を S := \emptyset で初期化する。
  2. 重み A[c] の大きい順にカードを取ることを試みる。カード c を取ろうとする時、 S \cup \{c\} が独立集合であれば、S に c を追加する。そうでなければ何もしない。
  3. 全てのカードをチェックした後の S が最適解である。

これが最適解を与えることの証明を与える。
(証明)*2
仮に S と異なる集合 T が最適解であったとする。両方とも極大なので、増加公理から |S| = |T| である。S の要素を A の値が大きい順に s_0, ..., s_{k - 1}, T の要素を A の値が大きい順に t_0, ..., t_{k - 1} とする。
初めて A[s_i] < A[t_i] が成り立つ i を j とする。C := {t_0, ..., t_j}, D := {s_0, ..., s_{j - 1}} と置くと、増加公理から C のある元 t_u があって D \cup \{t_u\} は独立。
ここで、A[t_u] >= A[t_j] > A[s_j] であるため、貪欲で s_j が選ばれたという事実と矛盾する。(終)

最後に、ある集合 S が独立集合であるかどうかの判定を行うアルゴリズムを考える。*3 左側 H 頂点、右側 W 頂点の二部グラフを考え、カード i を、左側の R[i] と右側の C[i] を結ぶ重み付きの辺とする。取ったカードたちによる部分グラフを考えた時、各連結成分に対して (辺の本数) <= (頂点の個数) であることが、独立であることと同値なので、各連結成分に対して辺の本数と頂点の個数を管理すればよい。これは UnionFind などを用いてできる。

登場する典型

実装上の注意点

とくになし。

提出: #7329715 (Rust)

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        n: usize, h: usize, w: usize,
        rca: [(usize1, usize1, i64); n],
    }
    let mut ans = vec![];
    for (r, c, a) in rca {
        ans.push((a, r, c));
    }
    ans.sort();
    ans.reverse();
    let mut uf = UnionFind::new(h + w);
    let mut tol = vec![1; h + w];
    let mut tot = 0;
    for &(val, r, c) in &ans {
        let v = c + h;
        if !uf.is_same_set(r, v) {
            let a = uf.root(r);
            let b = uf.root(v);
            let sum = tol[a] + tol[b];
            if sum >= 1 {
                uf.unite(a, b);
                tot += val;
                let root = uf.root(a);
                tol[root] = sum - 1;
            }
        } else {
            let a = uf.root(r);
            if tol[a] >= 1 {
                tot += val;
                tol[a] -= 1;
            }
        }
    }
    puts!("{}\n", tot);
}

まとめ

各行最大1個、各列最大1個のマトロイドは、交差が二部マッチングからなる独立性システムになるという事実がよく知られているが、それが交差ではなく合併になっても効率的に解けるという点で面白かった。

*1:行ごと最大1個、列ごと最大1個が明らかにマトロイドであり、(M, F) はこれらの合併なのでマトロイドである、という証明をインライン展開した。

*2:この証明は任意のマトロイドに適用できる。

*3:独立性オラクルとしてこのような単純なアルゴリズムが使えるのはおそらくこの問題特有で、一般にはマトロイドの合併の独立性オラクルの実装は難しい気がする。識者のツッコミ待ちです