kmjp's blog

競技プログラミング参加記です

TopCoder SRM 711 Div1 Hard TreeMoving、Div2 Hard TreeMovingDiv2

解けたと思ったけど計算量の見積もりが甘かった。
https://community.topcoder.com/stat?c=problem_statement&pm=14506
https://community.topcoder.com/stat?c=problem_statement&pm=14556

問題

M個の木を成すグラフT(i)がある。
各グラフはN頂点からなり、0~(n-1)のラベルが振られている。

ここで、以下の処理を行う。

  • 各グラフで任意の辺を1つずつ選び、取り除く。
  • T(i)で取り除いた辺の両端の頂点をu,vとすると、T((i+1)%M)のグラフでu-v間に辺を張る。

処理を行った後も各グラフが木であるような選び方は何通りか。

解法

T(i)でj番目の辺を取り除いたとき、次にT((i+1)%m)で取り除くことができる辺を列挙しよう。
これは全頂点間の距離などを用いれば容易にできる。

あとはT(0)で取り除く辺を総当たりし、以後それぞれT(1)、T(2)…と各辺を取り除く組み合わせを求めていき、最後にまたT(n-1)で取り除く辺に対し、最初にT(0)で選んだ辺を取り除くことができる場合の数を求めればよい。
この解法を愚直に書くとO(M*N^3)であり、Div2は通るがDiv1はTLEする。(自分もこれで落ちた)

これをもう少し高速化することを考える。
最初の「T(i)でj番目の辺を取り除いたとき、次にT((i+1)%m)で取り除くことができる辺を列挙しよう。」をもう少し賢くやろう。
T(i)でu-v間の辺を取り除くとき、T((i+1)%m)で取り除く辺の条件を考える。
T((i+1)%m)には最初u-v間の辺を追加するので、次に辺を取り除いた後T((i+1)%m)が木であるためには、もともとu-v間にあった辺のいずれかを切ればよい。
言い換えると、u-LCA(u,v)-v間の辺が切る対称となる。
先に前処理でLCA(u,v)を求めておくと、あとはimos法の要領で処理を高速化できる。

ll mo=1000000007;
vector<pair<int,int>> E[303][303];
vector<pair<int,int>> E2[303];

int par[303][303];
int pv[303][303];
int D[303][303];
int lca[303][303];
vector<int> O[303];
int dp[303][303];

class TreeMoving {
	public:
	int add(int& a,int b) {
		a += b;
		if(a>=mo) a-=mo;
		return a;
	}
	void dfs(int id,int cur,int pre,int d) {
		D[id][cur]=d;
		FORR(e,E[id][cur]) {
			if(e.first==pre) {
				par[id][cur]=pre;
				pv[id][cur]=e.second;
			}
			else {
				dfs(id,e.first,cur,d+1);
			}
		}
		O[id].push_back(cur);
	}
	int count(int n, vector <int> roots, vector <int> a, vector <int> b, vector <int> c) {
		int i,k,j,x;
		int m=a.size();
		FOR(i,303) FOR(k,303) E[i][k].clear();
		
		FOR(i,m) {
			E2[i].clear();
			ll X=c[i];
			FOR(j,n-1) {
				int u=(roots[i]+j+1)%n;
				int v=(roots[i]+(X%(j+1)))%n;
				E[i][u].push_back({v,j});
				E[i][v].push_back({u,j});
				E2[i].push_back({u,v});
				X = (a[i]*X+b[i])%mo;
			}
			O[i].clear();
			dfs(i,0,-1,0);
		}
		FOR(i,m) {
			FOR(k,n-1) {
				int u=E2[i][k].first;
				int v=E2[i][k].second;
				j = (i+1)%m;
				while(D[j][u]<D[j][v]) v=par[j][v];
				while(D[j][u]>D[j][v]) u=par[j][u];
				while(u!=v) v=par[j][v], u=par[j][u];
				lca[i][k]=u;
			}
		}
		
		ll ret=0;
		FOR(x,n-1) {
			ZERO(dp);
			dp[0][x]=1;
			FOR(i,m) {
				int sum[303]={};
				FOR(k,n-1) {
					add(sum[E2[i][k].first],dp[i][k]);
					add(sum[E2[i][k].second],dp[i][k]);
					add(sum[lca[i][k]],mo-dp[i][k]);
					add(sum[lca[i][k]],mo-dp[i][k]);
				}
				FORR(o,O[(i+1)%m]) if(o) {
					add(dp[i+1][pv[(i+1)%m][o]],sum[o]);
					add(sum[par[(i+1)%m][o]],sum[o]);
				}
			}
			ret += dp[m][x];
		}
		return ret%mo;
		
	}
}

まとめ

一応いくつかのケースでTLEしないこと確認して出したのだけど、ダメだったね。