SRM 682 div1 easy: SmilesTheFriendshipUnicorn

何もわかってなかった僕が言うのもなんなんですが何も考えず脳筋 dfs で通ってしまうのはちょっとアレですね…

問題

TopCoder Statistics - Problem Statement

解法

結局脳筋 dfs (各頂点からスタートして, パスの長さが 4 になるようなものがあるのかを調べる)で通るんですが, これの計算量が O(n^2) で通るのかは実は結構怪しいです(本番は計算量が怪しいという考えに至らなかった…まぁ幸運でしたが)。

例えば, ある頂点からスタートすると, たどる頂点の数が結局 O(n^2) になるような場合があります。

@btk15049 例えば、{0,0,0,1,2,3,4,4,4},{1,2,3,4,4,4,5,6,7}みたいなのがn^3くらい回りそうなのです。想定解法がn^2で回るdfsなら300点って残念すぎて悲しくなってきます・・・。

— nmnmnmnmnmnmnm (@enuemuenuemuenu) 2016, 2月 23

この場合は, O(n^2) になる頂点数が定数個しかないので大丈夫ですが, そんな感じで計算量が O(n^2) になるのかは結構怪しいところです。

想定解がどうなのかはよくわからないですが, 以下のような感じのが一番スッキリしそうです。

まず, ABCD を, 辺 2 つを選ぶことで決めます(O(E^2))。で, D から辺を引いて E と繋げたいですが, これはたかだか 5 本の隣り合った頂点を調べれば, E が存在するかがわかります。

bool vis[2222];

bool dfs(int now, int d, const vector<vi>& G) {
    vis[now] = true;
    if (d == 4) return true;
    for (int ch : G[now]) {
        if (vis[ch]) continue;
        if (dfs(ch, d+1, G)) return true;
    }
    vis[now] = false;
    return false;
}

class SmilesTheFriendshipUnicorn {
public:
    string hasFriendshipChain(int N, vector <int> A, vector <int> B) {
        vector<vi> G(N);
        int m = A.size();
        for (int i = 0; i < m; i++) {
            G[A[i]].push_back(B[i]);
            G[B[i]].push_back(A[i]);
        }
        for (int i = 0; i < N; i++) {
            memset(vis, false, sizeof(vis));
            if (dfs(i, 0, G)) return "Yay!";
        }
        return ":(";
    }
};