mayoko’s diary

プロコンとかいろいろ。

SRM 653 div1 med:Singing

答えみて書いただけでまだあんまり納得できてない・・・

問題:TopCoder Statistics - Problem Statement

解法:yosupoさんのページを参考にしました。

最小カットについて - よすぽの日記
このページでは,

・頂点がたくさんある。それを赤と青に塗り分ける。全部の頂点を必ず赤か青に塗らなくてはいけない
・必ず赤色に塗らなくてはいけない頂点(Sとする)と青色に塗らなくてはいけない頂点(Tとする)が存在する
・「Xが赤で、Yが青の時にZ円の罰金がかかる」という制約が沢山ある
・罰金の最小値は?

という問題は

・「Xが赤で、Yが青の時にZ円の罰金がかかる」ならX->Yに容量Zの辺を貼る
・SからTに最大流
・流せた量が答え

とすることで解けるとしています。今のところこれが正しいことを納得できてないのですが,これが正しいとしてグラフを作ると次のようにすればOKです。
頂点S,T,(1,...,N)を作る。
Aliceが担当する音階を青,Bobが担当する音階を赤とすると,条件より
Bobは1〜low-1の音階を担当しなければならないが,これはSからi(i=1〜low-1)へ容量∞の辺を貼ることで解決。
Aliceはhigh+1〜Nの音階を担当するのも,i(i=high+1〜N)からTへ容量∞の辺を貼ることで解決。
あとはBobとAliceが入れ替わったところで「もしAliceとBobで担当が入れ替わったら」コストが1かからなければならないが,これは制約として「pitch[i]が赤でpitch[i+1]が青なら1の罰金がかかる」と「pitch[i+1]が赤でpitch[i]が青なら1の罰金がかかる」というものであるので,両方向の辺を貼ればOK。
ということで問題を解くことができます。

この問題なんかとっつきにくいんですが,なにが問題を難しく感じさせているのかはわかった気がします。(今まで解いた最大フロー/最小カット問題が少なすぎるからかもしれませんが)よくある最小カット問題のグラフの構成は,制約条件の「選択肢」(例えばよくある仕事の割り当て二部マッチング問題の場合は「どのコンピュータが,どの仕事を担当するか」という選択肢)は辺の選び方に委ねられています。一方で,この問題の場合は選択肢(今回の場合は「音階をAliceとBobどちらが担当するか」)は頂点の方に委ねられています。そこがおそらくとっつきにくい方法であり,そこを見事に解決するのがyosupoさんの解法だったようです。

以下ソースコード

// max_flow
const int MAX_V = 2002;
const int INF = 1e6;
class FordFulkerson {
public:
    struct edge {
        int to;
        int cap;
        int rev;
        edge() {}
        edge(int t, int c, int r) : to(t), cap(c), rev(r) {}
    };
    vector<edge> G[MAX_V];
    void add_edge(int from, int to, int cap) {
        G[from].push_back(edge(to, cap, G[to].size()));
        G[to].push_back(edge(from, 0, G[from].size() - 1));
    }
    int max_flow(int s, int t) {
        int flow = 0;
        while (1) {
            for (int i = 0; i < MAX_V; i++) used[i] = false;
            int f = dfs(s, t, INF);
            if (f == 0) return flow;
            flow += f;
        }
    }
    void clear() {
        for (int i = 0; i < MAX_V; i++) G[i].clear();
    }
private:
    int dfs(int v, int t, int f) {
        if (v == t) return f;
        used[v] = true;
        for (int i = 0; i < G[v].size(); i++) {
            edge &e = G[v][i];
            if (!used[e.to] && e.cap > 0) {
                int d = dfs(e.to, t, min(e.cap, f));
                if (d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    bool used[MAX_V];
};

FordFulkerson ff;

class Singing {
public:
    int solve(int N, int low, int high, vector <int> pitch) {
        ff.clear();
        int s = 0, t = N+1;
        for (int i = 0; i < low; i++) ff.add_edge(s, i, INF);
        for (int i = high+1; i <= N; i++) ff.add_edge(i, t, INF);
        int n = pitch.size();
        for (int i = 0; i < n-1; i++) {
            if (pitch[i] != pitch[i+1]) {
                ff.add_edge(pitch[i], pitch[i+1], 1);
                ff.add_edge(pitch[i+1], pitch[i], 1);
            }
        }
        return ff.max_flow(s, t);
    }
}