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)である。

2016-10-02

SRM683 Div1 Easy "MoveStones"

問題

TopCoder Statistics - Problem Statement

Editorial

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

訳

まずは簡単に考えて、石の山が円状に並んでいないものとしよう。ちょうど、類題であるDiv2 Mediumでは石の山は直線状になっており、最後と最初の山が隣り合っていなかった。これの解法はO(n)の時間を要した。

円状の場合の解法は、石が山の間をn回以上移動する必要はなく、そのような動きは冗長である。なので、すべての隣り合う山において石を交換する必要はない。2つの山を左端・右端として(隣り合っていないとみなして)Div2バージョンのように解くことができる。よって、全てのO(n)の候補を試し、その最小値を返せばよい。

事後

「石が山の間をn回以上移動する必要はない」ってのがよく分からん！

ソースコード

class MoveStones {
    public:
    long long get(vector<int> a, vector<int> b) {
        int n = a.size();

        // おかしいやつ検出
        long long sa = 0, sb = 0;
        for (int i = 0; i < n; i++) {
            sa += a[i], sb += b[i];
        }
        if (sa != sb) return -1;

        // こっからおかしくないやつ
        long long ans = 1e18;
        // start地点を決めて回す（直線状と考える）
        for (int start = 0; start < n; start++) {
            long long cnt = 0;
            long long over = a[start] - b[start];
            for (int i = 0, cur = next(start, n); i < n - 1; i++, cur = next(cur, n)) {
                cnt += abs(over);
                over += a[cur] - b[cur];
            }
            // 最小をとっていく
            ans = min(ans, cnt);
        }

        return ans;
    }

    // 次のindexを返す
    int next(int i, int n) {
        return i + 1 == n ? 0 : i + 1;
    }
};

2016-10-02

SRM684 Div1 Easy "CliqueParty"

問題

TopCoder Statistics - Problem Statement

解法

配列を昇順にソートしておいて、サブセットに含める最小値a[L]と最大値a[R]の２つを決め打ちする。
すると、Dの最大値は「a[R] - a[L]」に固定される。Dの最小値も「Dの最大値 / k」に固定される。
あとはa[L + 1]からa[R - 1]まで順に走査し、最近使用した左のものとの差、およびa[R]との差がDの最小値以上のものを貪欲に選んでいけばよい。

ソースコード

class CliqueParty {
    public:
    int maxsize(vector<int> a, int k) {
        int n = a.size();
        sort(a.begin(), a.end());
        int ans = 2;
        for (int L = 0; L < n; L++) {
            for (int R = L + 1; R < n; R++) {
                // (i, j)の範囲内とする。
                int ma = a[R] - a[L];
                int mi = ma / k + (ma % k == 0 ? 0 : 1);

                // 貪欲に行こう
                int cnt = 0;
                int pre_val = a[L];
                for (int i = L + 1; i < R; i++) {
                    if (mi <= a[i] - pre_val && mi <= a[R] - a[i]) {
                        cnt++;
                        pre_val = a[i];
                    }
                }

                if (ans < 2 + cnt) {
                    ans = 2 + cnt;
                }
            }
        }
        return ans;
    }
};

プロフィール

id:Ekaing

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

このブログについて

SRM

Codeforces

AtCoder Regular Contest

#014

#013