WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM682 Div1 Easy "SmilesTheFriendshipUnicorn"

考えた解法

普通にdfsで探索すると計算量がやばい。
特に下図のような構成となっているグラフで、赤い頂点から探索を進めた日にゃあスタート頂点1つにつき計算量がO(M^2)になる。やばい。
f:id:Ekaing:20161002230052p:plain

あれ待てよ・・・赤い頂点って・・・そんなに無くね?・・・いけるんじゃね?

いやいや、2000のルートだけグラフを分割して
f:id:Ekaing:20161002230712p:plain
こーんなグラフで来やがるかもしれんぞ・・

あれでも45(2000のルート)^3で計算終わるな・・・

・・・

普通にdfsで探索しても計算量はいける。

ソースコード
int N;
vector<int> G[2020];
bool use[2020];

class SmilesTheFriendshipUnicorn {
    public:
    string hasFriendshipChain(int _N, vector<int> A, vector<int> B) {
        N = _N;

        // グラフ作成
        for (int i = 0; i < N; i++) {
            G[i].clear();
        }
        for (int i = 0; i < A.size(); i++) {
            G[A[i]].push_back(B[i]);
            G[B[i]].push_back(A[i]);
        }

        // スタートとなる頂点で回す
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                use[j] = false;
            }
            // dfsで探索
            if (dfs(i, 1)) return "Yay!";
        }
        return ":(";
    }

    bool dfs(int cur, int num) {
        if (num == 5) return true;
        use[cur] = true;
        for (int i = 0; i < G[cur].size(); i++) {
            int next = G[cur][i];
            if (use[next]) continue;
            if(dfs(next, num + 1)) return true;
        }
        use[cur] = false;
        return false;
    }
};

Editorial

https://apps.topcoder.com/wiki/display/tc/SRM+682

この問題はいくつかのアプローチがある。1つに、「a->b->c->d」というような4つの異なる頂点のパスを見つけ出す方法を考えればよいと、問題を簡単にしてしまう方法がある。このようなパスを見つけることができたら、あとはそこに繋がる頂点iを見つける必要があるだけである。4つの長さのパスを全て列挙したとして、aに接続したiを探すことになる。それはa, b, c,そしてdとは異なる最初のiであればよく、aと隣接した頂点を走査すれば、高々5回試せばよい。なので、要する計算量は長さ4のシンプルパスの数に5を掛けたものとなる。

長さ4のシンプルパス

長さ4のシンプルパスは[a->b, b->c, c->d」のような3つの辺で構成される。この問題のグラフにおいて辺の数Mは高々2000であるため、「a->b, c->d」といった隣接した頂点のペアは高々O(M^2)である。それぞれにおいて、「b->c」といった中間の辺で繋がっているかを確認する。これは頂点が他の頂点と隣接しているかのマトリクスを予め計算しておけばO(1)となる。「a->b->c->d」が繋がっていることを確認できたら、最後に全ての頂点が異なることを確認する。この方法では、長さ4のシンプルパスを見つけるためにO(M^2)の計算量を要する。上記の通り、高々5回の計算で5つ目の頂点が見つかるため、全体の計算量もO(M^2)である。