TopCoder SRM 622 Div1
こんにちはtatsyです。
今回はSRM622の解説です。
Easy (250点)
問題
ある国にはN個の街があり、このN個の街は完全有向グラフをなしている。この国にはアルゴリズムの日という日があり、この日には全ての街のペア(i, j)の間をバスが運行する。このバスは常に最短のパスを通ってiからjに向かうのだが、もし最短のパスが複数ある場合には運転手が任意の経路を選んでよいことになっている。この国の道路は老朽化が進んでいて、T回以上バスが通ると壊れてしまう。グラフの情報が与えられたとき、修理が必要な道路の総距離を答えよ。
解法
有向グラフのエッジが最短パスに何回含まれるかを数える問題ということになる。数え終わったらT回以上含まれているエッジの長さを足し上げていけば答えになる。
自分は結構泥臭い実装にした。Dijkstra法で全てのペア(i, j)について最短パスを求めに行くのだけど、このときバックトラックできるようにパスを保存しておく。
全てのパスが計算し終わったら、バックトラックをして何回パスを通過するのかを数える。このとき重複で数えないように(i, j)のペアに固有のIDを割り当てて数え上げた。
このやり方だとペアの数がV^2でダイクストラ法の計算量は(V+E)logV = V^2 logV になるので、全部ではV^4 logVになる。コードだと下のような感じになる。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
using namespace std;
typedef long long lint;
typedef pair<lint,lint> pll;
#define REP(i,n) for(int i=0; i<n; i++)
#define REPP(i,s,e) for(int i=s; i<=e; i++)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
typedef pair<int,int> P;
const int INF = 1<<20;
int path[55][55];
int dist[55];
set<int> pre[55];
set<int> use[55][55];
class BuildingRoutes {
public:
int n;
void calc(int f, int t) {
REP(i,n) {
dist[i] = INF;
pre[i].clear();
}
priority_queue<P, vector<P>, greater<P> > que;
que.push(P(0, f));
dist[f] = 0;
while(!que.empty()) {
P p = que.top();
que.pop();
if(p.second == t) continue;
for(int i=0; i<n; i++) {
if(i == p.second) continue;
int d_new = dist[p.second] + path[p.second][i];
if(dist[i] > d_new) {
pre[i].clear();
pre[i].insert(p.second);
dist[i] = d_new;
que.push(P(d_new, i));
} else if(dist[i] == d_new) {
pre[i].insert(p.second);
}
}
}
int id = f * n + t;
queue<int> q;
q.push(t);
while(!q.empty()) {
int cur = q.front();
q.pop();
if(pre[cur].empty()) continue;
for(auto it=pre[cur].begin(); it!=pre[cur].end(); ++it) {
int fr = *it;
if(use[fr][cur].count(id) == 0) {
use[fr][cur].insert(id);
q.push(fr);
}
}
}
}
int build(vector <string> d, int T) {
this->n = d.size();
REP(i,n) REP(j,n) {
path[i][j] = d[i][j] - '0';
}
REP(i,n) REP(j,n) use[i][j].clear();
REP(i,n) {
REP(j,n) {
if(i != j) {
calc(i, j);
}
}
}
int ret = 0;
REP(i,n) {
REP(j,n) {
if(use[i][j].size() >= T) ret += path[i][j];
}
}
return ret;
}
};
コンテストの後に分かったことだけど、上の問題にはもう少し効率が良くて、見通しの良いやり方がある。
まずWarshall-Floyd法で全ての街の間の最短距離を求めておく。このとき2つの街a, bを直接結ぶエッジが最短経路に入っているなら、
(i, j)間の最短経路長 = (i, a)の最短経路長 + エッジ(a, b)の長さ + (b, j)の最短経路長
となるはずである。
このアイディアを利用すると、Warshall-FloydにV^3, 最短パスの数え上げにV^4なので全体ではV^4の計算量になって効率があがる。しかも実装も圧倒的に簡単。
計算量的に上のやり方でも通ったから良かったけど、街が最大100個だったら終わってたなと反省。
Medium (500点)
問題
ある会社のネットワークは木構造をなしている。このネットワークをいくつかの部分ネットワークに分割したい。このとき条件があって、ネットワークを形成ケーブルの長さについて部分ネットワークの直径(木構造の意味での直径)がK以下になってほしい。できるだけ部分ネットワークの数を少なくしたい時、条件を満たす最小の部分ネットワーク数はいくつか？
解法
まずコードの見通しをよくするために、木の直径を求める方法を簡単に復習。
ノードvを根とする木構造Tvを考える。vには子としてu1, …, ukが接続されているとする。この場合、木の直径となる経路Dとvとの関係は次の2つのうちのいずれかになる。
- Dがvに含まれる。この場合、木の直径はvから1番離れた葉ノードまでの距離と2番目に離れた葉ノードまでの距離の合計。
- Dがvを含まず、u1からukのいずれか1つをDが含む。この場合は、再帰的に子ノードを探索して半径を求める必要がある。
という感じで、木構造の半径は再帰により求まる。このアイディアを応用して問題を解く。
まず、木構造をどう作るかだけど、上のやり方だと根から子に向かっていく方向の探索しかなく逆に戻れる必要はないので、今回の問題のケースでいえば0を根とする木構造で親から子への有向辺だけを持つようなグラフを作る。
このグラフを根、すなわち0のノードから探索していく。再帰の段階では部分木構造の根から下を考えればよいので、今、部分木構造の根としてノードvが渡されたと考える。
vを根とする部分木構造を直径がKを超えない木に分割するとき、vの直接の子のうちどれを切らずに残すかを考えればいい。ただ、どれを残すかを全ての場合について調べてしまうと指数時間の計算量になってしまうので、もう少し工夫する。
今回の問題では木の直径が多くとも500なので、これを利用できないか考える。そうすると(だいぶ考えて)
dp[注目ノード][今考慮すべき最後の子ノード][使える長さ]
というDP表を持てばよいのではないかと分かる(と思う)。
なので、再帰関数にはメモ化深さ優先探索の要領で3つの数を渡す。関数で処理すべき内容は、考慮すべき最後の子ノードを切り落とすのか残すのか、そして残すとしたら長さをどのくらいその子ノード以下の部分木に割り当てるのかを考える問題になる。
と、そんな感じのアイディアをコードにすると下のような感じになる。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
using namespace std;
typedef long long lint;
typedef pair<lint,lint> pll;
#define REP(i,n) for(int i=0; i<n; i++)
#define REPP(i,s,e) for(int i=s; i<=e; i++)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
struct edge{ int to, dist; };
const int INF = 1 << 25;
vector<edge> G[55];
int dp[55][55][550];
class Ethernet {
public:
int n, K;
int calc(int v, int last, int hi) {
if(last < 0) return 0;
int& ret = dp[v][last][hi];
if(ret == -1) {
ret = INF;
edge& e = G[v][last];
// cut off last leaf
ret = calc(v, last-1, hi) + calc(e.to, G[e.to].size()-1, K) + 1;
// keep last leaf
for(int k=0; k+e.dist <= hi; k++) {
int val = calc(e.to, G[e.to].size()-1, k) + calc(v, last-1, min(hi, K - (k+e.dist)));
ret = min(ret, val);
}
}
return ret;
}
void add_edge(int f, int t, int d) {
edge e = { t, d };
G[f].push_back(e);
}
int connect(vector <int> parent, vector <int> dist, int maxDist) {
this->K = maxDist;
this->n = (int)parent.size() + 1;
REP(i,n) G[i].clear();
for(int i=0; i<n-1; i++) {
int p = parent[i];
add_edge(p, i+1, dist[i]);
}
memset(dp, -1, sizeof(dp));
return calc(0, G[0].size()-1, K) + 1;
}
};
まとめ
今回のEasyは問題開いた瞬間のひらめかなさがすごかったです。結果的に全くひらめかずかなり泥臭い実装になってしまいました(通ったから良かったけど)。
MediumはDPにすればよいんだなと思うところまでは良いとして、再帰関数の実装が結構細かくて厄介だと思いました。
週末はGCJなのでTシャツ取れると良いな、という感じで今回の解説を終わります。
お読みいただき、ありがとうございました。