WARush

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

SRM627 Div1 Medium "GraphInversions"

問題

TopCoder Statistics - Problem Statement

あなたはN個のノードを持つ連結した無向グラフが与えられる。ノードには0からN-1の番号が付けられている。このグラフの特徴としてエッジの数はノードの数と同じ事があげられる。あなたはグラフを表現したものとしてint配列のA, B, Vが与えられる。3つの配列はそれぞれN個の要素をもつ。ノードA[i]とB[i]がエッジで繋がっており、セルフループしていたり、多重辺となっていることはない。また、ノードには値が設定されており、ノードiの値はV[i]である。

私達はこのグラフのシンプルパスに興味を持っている。シンプルパスは同じノードが2つ以上使われていることない、ノードのシーケンスであり、隣り合うノードはエッジで繋がっているものである。任意のシンプルパスは、それぞれのノードをそのノードに設定された値に置き換えて、値の並びに書き換えることができる。私達はその並びをシンプルパスの"value list"と呼んでいる。

整数のシーケンスSの反転度は、i < j であるが、 S[i] > S[j] であるような、(i, j)のペアの数として表される。例えばシーケンスSが{10, 30, 20, 20}であれば、(1, 2)と(1, 3)で反転しているため、Sの反転度は2である。

あなたは上記のようなフォーマットで与えられるグラフ Gと整数 Kが与えられる。Gにおいて、K以上のノードを持った全てのシンプルパスについて考える。そのようなシンプルパスがなければ-1を、そうでなかれば、最も少ない反転度を返せ。

制約

3 <= N <= 1000
1 <= V[i] <= 1000
1 <= K <= N


考えたこと

まず、シンプルパスにKより多くノードを使うメリットはないので、考えるシンプルパスの長さはKとする。

シンプルパスの始点となるノードを決め打ちして、そのノードからDFSでシンプルパスを作成していくと、計算量はどんなもんかな?

まず始点の数=ノードの数はN。

次に、DFSで訪れるノードの数は、グラフは木ではないのでNより多くなる。循環するところは2倍になるから、最悪パターンは全てのノードで大きな輪っかを作っていた場合で、それだと訪れるノードの数はN * 2。まあNでいいか。

最後にノードを訪れた時の反転度の更新は、今まで訪れたノードの値をソートされたリストで持っておき、現在のノードより小さな値を持つノードの数をupper_bound的なもので調べればよいからlog N。

全体でO(N^2 * log N)だからいける

事後

TLE


解法

上の解法だと、新しくノードを訪れるたびにリストのコピーをしなければならないので、O(N^3)となってTLEしたんじゃなかろうかと予想。

赤い人を見たところ、BIT(Binary Indexed Tree)を使用して『今まで訪れたノードの値セットの中から、新しく訪れたノードの値よりも小さいものは何個あるか?』を計算してた。

これだと今度こそ本当にO(N^2 * log N)

ソースコード

vector<int> G[1050];
vector<int> V;
int res;
int K;
bool used[1010];
int bit[1010];

vector<int> R;
int cnt;

class GraphInversions {
public:

    int getMinimumInversions(vector <int> A, vector <int> B, vector <int> _V, int _K) {
        int N = A.size();
        V = _V;
        K = _K;

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

        res = (int)1e9;
        memset(used, false, sizeof(used));
        
        // 始点を決めてDFS
        for (int i = 0; i < N; i++) {
            dfs(i, 0, 0);
        }

        if (res == (int)1e9) return -1;
        return res;
    }

    void dfs(int v, int cost, int len) {

        used[v] = true;
        len++;
        update(V[v], 1);

        if (len == K) {
            // K個ノードを使ったら答え更新
            res = min(res, cost);
        }
        else {
            // 次なるノードを総当り
            for (int i = 0; i < G[v].size(); i++) {
                int to = G[v][i];
                if (used[to]) continue;
                // 今まで訪れたノードの中で、
                // 新しく訪れるノードよりも小さい値を持っていた
                // ノードの数を算出
                int add = quary(V[to] - 1);
                dfs(to, cost + add, len);
            }
        }

        used[v] = false;
        update(V[v], -1);
    }

    // i番目までの値の合計を返す
    int quary(int i) {
        int r = 0;
        while (i > 0) {
            r += bit[i];
            i -= i & -i;
        }
        return r;
    }

    // i番目の値にvを足す
    void update(int i, int v) {
        while (i <= 1000) {
            bit[i] += v;
            i += i & -i;
        }
    }
};