CODE FESTIVAL 2015 決勝 F - 歩くピアニスト

問題

code-festival-2015-final-open.contest.atcoder.jp

解法

解説見るのがわかりやすいと思いますが一応こっちでも書きます。

まず問題を言い換えます。頂点を通った回数だとわかりづらいので, ド⇔レ の辺を通った回数, レ⇔ミ の辺を通った回数, ..., シ⇔ド の辺を通った回数を求めます。ド⇔レを通った回数を x とすれば, レを押す回数の分 * 2 回だけ レ をつなぐ辺を通るので, レ⇔ミ を通る辺の回数は 2*C[1] - x と求まります。同様にやって行くと, ド⇔レ を通る回数が 2 通りの方法で求まるので, x が求まります。

このようにして各辺を通った回数が求まったら, まずそれらの中で負の数になっているものがないかをチェックします。
これがなければ, あとはグラフがオイラー路になっているかを確かめればよいです(つまり各頂点の次数が偶数でありかつ連結)が, 先ほどのアルゴリズム的に各頂点の次数は明らかに偶数なので, 連結性を確かめれば良いです。

得た知見

• オイラー路, 毎回次数が偶数なことしか思い出さないけど連結なことも重要な要素なんだよな

ll C[7];

struct UnionFind {
    vector<int> par;
    int n, cnt;
    UnionFind(const int& x = 0) {init(x);}
    void init(const int& x) {par.assign(cnt=n=x, -1);}
    inline int find(const int& x) {return par[x] < 0 ? x : par[x] = find(par[x]);}
    inline bool same(const int& x, const int& y) {return find(x) == find(y);}
    inline bool unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return false;
        --cnt;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    inline int count() const {return cnt;}
    inline int count(int x) {return -par[find(x)];}
};

void no() {
    cout << "NO" << endl;
    exit(0);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    for (int i = 0; i < 7; i++) cin >> C[i];
    C[0]--;
    ll x = C[0] - C[6] + C[5] - C[4] + C[3] - C[2] + C[1];
    UnionFind uf(10);
    for (int i = 0; i < 7; i++) {
        if (x < 0) no();
        if (x > 0) uf.unite(i, (i+1)%7);
        x = 2*C[(i+1)%7] - x;
    }
    for (int i = 0; i < 7; i++) {
        if (C[i] > 0) {
            if (!uf.same(0, i)) no();
        }
    }
    cout << "YES" << endl;
    return 0;
}