SRM 668 div1 med:WalkingToSchool

問題

解法

この問題では閉路が重要なポジションを占めています。

例えば, サンプル 1) を見てみましょう。

このグラフでは, (0, 1) という閉路と, (0, 1, 2) という閉路があります。

この閉路の長さ 2 と 3 の最大公約数は 1 です。なので, 十分大きな K に対して, 長さ K で 0 -> 1 に行く方法及び 1 -> 0 に行く方法があるわけです。

これをメインアイデアとして, 更に具体的なところを詰めます。

まず, 各頂点からはどの閉路を使えるのかを調べます(dfs でやっているところ)。これは, 各頂点 s をスタートとして, ぐるっと回って再び頂点 s にたどり着くのにかかる長さを調べれば良いです。結局大事なのは最大公約数なので, それのみを覚えておきます。

次に, 各頂点から, どの頂点にたどり着けるのかを調べます(cfs でやっているところ)。これらを調べることにより, 頂点 0/1 から, どの閉路を利用できるのかがわかります。
例えば頂点 0 から頂点 1 に向かうときには, 0 -> 頂点 i -> 1 というような軌跡をたどります。

そのため, 頂点 i を通るループを利用するためには,
・0 から i に行くことができる
・i から 1 に行くことができる
という条件を満たしている必要があります。この条件を満たしている場合は, その閉路を使って長さを調整できます。

得た知見

閉路検出は O(NM) でできる
- 割と「閉路検出どうやろうかー」と悩んでいた

vector<int> G[2020];
int loop[2020];
bool visit[2020];

void dfs(int v, int s, int d) {
    visit[v] = true;
    for (int to : G[v]) {
        if (to == s) {
            loop[s] = __gcd(loop[s], d+1);
        } else if (visit[to]) continue;
        else {
            dfs(to, s, d+1);
        }
    }
}

bool can[2020][2020];

void cfs(int v, int s) {
    can[s][v] = true;
    for (int to : G[v]) {
        if (can[s][to]) continue;
        cfs(to, s);
    }
}

class WalkingToSchool {
public:
    string canWalkExactly(int N, vector <int> from, vector <int> to) {
        //cout << "TEST" << endl;
        const string C = "Chores", F = "Freedom";
        int M = from.size();
        for (int i = 0; i < N; i++) {
            G[i].clear();
            loop[i] = 0;
        }
        for (int i = 0; i < M; i++) {
            G[from[i]].push_back(to[i]);
        }
        for (int i = 0; i < N; i++) {
            memset(visit, false, sizeof(visit));
            dfs(i, i, 0);
        }
        //for (int i = 0; i < N; i++) cout << loop[i] << endl;
        memset(can, false, sizeof(can));
        for (int i = 0; i < N; i++) {
            cfs(i, i);
        }
        {
            int g = 0;
            for (int i = 0; i < N; i++) {
                if (!can[0][i] || !can[i][1]) continue;
                g = __gcd(g, loop[i]);
            }
            if (!can[0][1] || g != 1) return C;
        }
        {
            int g = 0;
            for (int i = 0; i < N; i++) {
                if (!can[1][i] || !can[i][0]) continue;
                g = __gcd(g, loop[i]);
            }
            if (!can[1][0] || g != 1) return C;
        }
        return F;
    }
};

mayoko’s diary

プロコンとかいろいろ。

SRM 668 div1 med:WalkingToSchool

問題

解法

得た知見