SRM 496 div1 med:OneDimensionalBalls

問題

解法

まず, 問題をもうちょっと噛み砕いてみます。

m = firstPicture.size, n = secondPicture.size とします。

まず, 場合分けとしては「firstPicture と secondPicture でどれだけボールが移動したか」ということにのみ注意すれば良いことに気づきます。もっというと, firstPicture の一番左端のボールと secondPicture[j] の距離で場合分けすれば良いです。
これで, 調べるべき距離は n 通りにまで狭まりました。

上で決まった距離 d を用いると, firstPicture のそれぞれのボールが行き着く先は, たかだか 2 通りに決まります。つまり,
abs(firstPicture[i] - secondPicture[j]) == d となる j のみです。secondPicture のそれぞれの値は異なるという条件から, このような j はたかだか 2 通りしかありません。ということで, 上記の等式を満たす２つの組を結んだ 2 部グラフを考えます。問題で聞かれていることは, この 2 部グラフが最大マッチングを取るような辺の選び方は何通りあるか, ということです。
これで問題をやや定式化出来ました。次はこの問題をどう解くかを考えてみます。

実はこの 2 部グラフには都合の良い特徴があります。先ほど言ったように, 各頂点はたかだか 2 の次数を持たないこともそうですが, より嬉しいこととして, 「この 2 部グラフは閉路がない」ということが言えます。簡単に言うと閉路があると距離 d 離れているはずがもっと離れることになるからです。

このことから, この 2 部グラフは道(path) がバラバラに存在していることになります。例えば, 以下のような感じです。
f:id:mayokoex:20151104181837j:plain

この図では, 赤い path と青い path の 2 つがありますね。

この path の両端の頂点が secondPicture のボールか, firstPicture のボールかで場合分けします。
まず, 両端の頂点が firstPicture だった場合, firstPicture の頂点をすべてマッチングすることが出来ないので, 0 通り
片方の頂点が secondPicture だった場合(図の青い path), 1 通りだけマッチングする方法があります。
両方の頂点が secondPicture だった場合(図の赤い path), secondPicture 側の頂点の数だけマッチング方法があります。図の場合だと 3 通りです。

これらを, すべて掛け算すれば最大マッチングの場合の数を求められます(path はそれぞれ独立しているので)。

const int MAXN = 55;
bool used[2*MAXN];

class OneDimensionalBalls {
public:
    long long countValidGuesses(vector <int> fP, vector <int> sP) {
        sort(fP.begin(), fP.end());
        sort(sP.begin(), sP.end());
        int n = sP.size(), m = fP.size();
        ll ret = 0;
        for (int i = 0; i < n; i++) {
            if (fP[0] == sP[i]) continue;
            int dist = abs(fP[0]-sP[i]);
            // 二部グラフを作る
            vector<vector<int> > G(n+m);
            for (int j = 1; j < m; j++) for (int k = 0; k < n; k++) {
                if (k == i) continue;
                if (dist == abs(fP[j]-sP[k])) {
                    G[j].push_back(k+m);
                    G[k+m].push_back(j);
                }
            }
            ll ans = 1;
            memset(used, false, sizeof(used));
            used[0] = used[m+i] = true;
            for (int j = 1; j < m; j++) {
                if (used[j]) continue;
                queue<int> que;
                que.push(j);
                int u = -1, v = -1, cnt = 0;
                while (!que.empty()) {
                    int now = que.front(); que.pop();
                    cnt++;
                    used[now] = true;
                    if (G[now].size() == 1) {
                        if (u == -1) u = now;
                        else v = now;
                    }
                    for (int el : G[now]) {
                        if (!used[el]) {
                            que.push(el);
                        }
                    }
                }
                if (v == -1 || (u < m && v < m)) ans *= 0;
                if (u > v) swap(u, v);
                if (u < m) ans *= 1;
                else ans *= (cnt+1)/2;
            }
            ret += ans;
        }
        return ret;
    }
};

mayoko’s diary

プロコンとかいろいろ。

SRM 496 div1 med:OneDimensionalBalls

問題

解法