TopCoder Open 2015 Round 1A

Tatsuya Yatagawa
Programming Contest

こんにちはtatsyです。本日はTCO2015ラウンド1Aの解説です。

Easy (250点)

問題

ある2つの数A,Bが与えられた時、この二つの数の類似度sim(A,B)は0から9の数字の中で、2つの数両方に含まれる数の個数を表す。AとBが取りうる値の下限Lと上限Rが与えられたとき、互いにことなるAとBでsim(A,B)の最大値はいくつか？

解法

単純に考えるとLとRの間の全ての数のペアについてsimがいくつになるかを見ればいいのですが、Rは最大で100,000まであるので、計算量的には間に合いません。

この問題では数字にどんな数が含まれているかだけが関心事なので、桁の並びの順番は無視できます。ですので、実際に考慮すべき数字の並びはもっと少なくなります。

例えば、11111という数なら数は1しか出てこないので、これは1と同義ですし、13245という数があれば、これは12345と同義と解釈できます。

なので、この略した数字をmapで管理して、どの並びが何種類出てくるのかを記録することにします。

もし、2種類以上出てくるのであれば、この並びに含まれる数の個数がsimになりますので、その最大値を求めます。

上の計算だと完全に出てくる数字が一致する場合にしか対応できないので、一致が起こらなかった場合については、mapに入っている数字の並びのペアをとって、simがいくつになるのかを計算してあげます。

さて、そうすると最後のペアの計算にはmapに含まれるパターンの数をmとしてO(m^2)の計算量がかかります。これで計算量が大丈夫なのかを考察してみます。

数は高々5桁で重複がないので、出てくる数はおおよそ10 * 9 * 7 * 8 * 6 = 30240個です。さらに並び順は無視できることから、これを5! = 120で割ってよく、mはだいたい300くらいであることが分かります。

たぶん正確にはC(n,m)をn個からm個を重複なく選ぶ場合の数として、C(10,1) + C(10,2) + C(10,3) + C(10,4) + C(10,5)個のパターンがあります(オーダーはそんなに変わらない)。

なので、計算量的には大丈夫で、この解法でテストが通ります。

class Similars {
public:
    map<string, int> mp;

    string toS(int x) {
        string ret = "";
        while (x != 0) {
            ret = (char)('0' + (x % 10)) + ret;
            x /= 10;
        }
        return ret;
    }

    int count(string s) {
        set<int> st;
        for (int i = 0; i < s.size(); i++) {
            st.insert(s[i]);
        }
        return st.size();
    }

    int sim(string s1, string s2) {
        int ret = 0;
        for (int i = 0; i < s1.size(); i++) {
            for (int j = 0; j < s2.size(); j++) {
                if (s1[i] == s2[j]) {
                    ret++;
                    break;
                }
            }
        }
        return ret;
    }

    int maxsim(int L, int R) {
        mp.clear();
        for (int i = L; i <= R; i++) {
            string s = toS(i);
            sort(s.begin(), s.end());
            s.erase(unique(s.begin(), s.end()), s.end());
            mp[s]++;
        }

        int ans = 0;
        vector<string> v;
        for (auto it : mp) {
            if (it.second >= 2) {
                ans = max(ans, (int)it.first.size());
            }
            v.push_back(it.first);
        }

        for (int i = 0; i < v.size(); i++) {
            for (int j = i + 1; j < v.size(); j++) {

                ans = max(ans, sim(v[i], v[j]));
            }
        }
        return ans;
    }
};

Medium (500点)

問題

今、横にNマスのマス目が与えられていて、各マス目からは矢印が伸びています。この矢印は始点は互いに異なっていますが、終点は同じになる可能性があります。

また自分から自分への矢印というのも存在する可能性が有ります。このとき、あなたは、Nマスのうちで好きなマスを適当にえらび、そこに駒をおきます。駒が置いてあるマスで矢印の終点に向かって駒を動かすという操作をK回行う仮定の中で、1マスに2つ以上の駒が入ることがなければあなたの勝ちです。

このとき、あなたが勝利できる駒の置き方は何通りあるでしょうか？

解法

駒の置き方の置換を考える問題です。このとき、置換はN×Nの行列で各列で1つの要素だけが1になったようなもので表せます。

ポイントとして置換をK回行った時に同じマスに駒が入るというのは、置換行列をK回かけたときに同じ行に2つ以上の1が並ぶということと同義です。

ですので、行列をK回かけていく計算をしながら、同じ行に2つ以上の1が現れたら、それらは同時に駒を置けないグループとしてUnion-Find木なので管理しておきます。

最終的に同時に駒を置けないグループが出来上がったら、そのグループ内では駒を置かないか、そのグループ内の1つに駒を置くかのどれかになるので、i番目のグループに含まれるマスの数をx[i]として

(1 + x[0]) (1 + x[1]) … (1 + x[m])

というのが答えになります。

さて、あとはKがとても大きくなる可能性があるため、置換行列をK回もかけられないという部分ですが、置換行列は高々その行列のランクの数だけかければ巡回します。

ですので、この場合、行列のサイズであるN回行列をかければ十分ですので、Kがどんなに大きくても、高々50回行列をかける計算をすれば十分です。

class uftree {
public:
    int n;
    vector<int> val;
    uftree(int n_) : n(n_), val(n_, -1) {}
    int root(int x) { return (val[x] < 0) ? x : (val[x] = root(val[x])); }
    void merge(int x, int y) {
        x = root(x); y = root(y); if (x == y) return;
        val[x] += val[y];
        val[y] = x;
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }

    int independent() {
        int ret = 0;
        for (int i = 0; i<n; i++) if (val[i] < 0) ret++;
        return ret;
    }
};

const lint mod = (lint)1.0e9 + 7;
int matA[55][55];
int matB[55][55];
int matC[55][55];

class Autogame {
public:
    int n;

    void multi() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int val = 0;
                for (int k = 0; k < n; k++) {
                    val += matA[i][k] * matB[k][j];
                }
                matC[i][j] = val;
            }
        }
        memcpy(matB, matC, sizeof(matC));
    }

    int wayscnt(vector<int> a, int K) {
        this->n = a.size();


        uftree tree(n);
        memset(matA, 0, sizeof(matA));
        memset(matB, 0, sizeof(matB));
        for (int i = 0; i < n; i++) {
            matA[a[i] - 1][i] = 1;
            matB[i][i] = 1;
        }

        int m = min(n, K);
        vector<int> row;
        for (int t = 0; t < m; t++) {
            multi();
            for (int i = 0; i < n; i++) {
                row.clear();
                for (int j = 0; j < n; j++) {
                    if (matB[i][j] == 1) {
                        row.push_back(j);
                    }
                }

                if (row.size() > 1) {
                    for (int k = 1; k < row.size(); k++) {
                        tree.merge(row[0], row[k]);
                    }
                }
            }
        }

        lint ans = 1;
        for (int i = 0; i < n; i++) {
            if (tree.val[i] < 0) {
                int cnt = 0;
                for (int j = 0; j < n; j++) {
                    if (tree.same(i, j)) {
                        cnt++;
                    }
                }
                ans = (ans * (cnt + 1)) % mod;
            }
        }

        return (int)ans;
    }
};

まとめ

今回はどちらかというとEasyの方が、きっちり答えを合わせるのは難しかったような気がします。かなり問題文のテストケースが弱かったので、
もう少しChallenge祭りになるかなぁと思ったのですが、それほどではなかったみたいですね。

Mediumについては、結構簡単めの問題で、出来ている人もかなりいたみたいです。かく言う僕も、初めてMedium当てられました。

まぁTCOなので難易度設定は簡単めではあったとは思いますが。

というわけで、今回の解説は終わります。最後までお読みいただき、ありがとうございました。