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; } } };