Hatena::Grouptopcoder

kojingharangの日記 RSSフィード

 | 

2014-05-23

SRM 621 Div1 500 TreesAnalysis

21:07 | SRM 621 Div1 500 TreesAnalysis - kojingharangの日記 を含むブックマーク はてなブックマーク - SRM 621 Div1 500 TreesAnalysis - kojingharangの日記 SRM 621 Div1 500 TreesAnalysis - kojingharangの日記 のブックマークコメント

  • 頂点 0〜N-1 を持つ木が2つ与えられる。それぞれの木から1辺ずつ(e1, e2)選んで消すとそれぞれの木は2つの部分に分かれる。
  • それぞれの木からどちらかの部分を選んだ時、どちらの部分にも含まれる頂点ラベルの個数^2の最大値をS(e1, e2)とする。
  • 全ての辺に対して S(e1, e2) の和を求めよ。2≦頂点数≦4000
  • ファッ！？
  • なんてややこしいんだ
  • シミュレーションを書いてみる
  • それぞれの辺に対して頂点→片方の部分に含まれるかどうか bitset<4000> に持っておいて
  • 全ての e1, e2 について bitset の and, ~and, and~, ~and~ のbitを数える
  • O(N^2)だけど定数項が大きいのでだめそう
  • それしか思いつかないので提出 → challenge phase なぜか生き残る → failed system test
  • (あとで)

■ ポイント1

  • 0 を根だとして、頂点 n1 in Tree1, n2 in Tree2 に対して
  • 「n1 以下(n1とその子孫)の頂点ラベル集合 ∩ n2 以下の頂点ラベル集合」の個数 Xect[n1][n2] と
  • n1 以下の頂点の個数 size[木][n1] がわかっていれば答えが求まる
|n1以下の集合 ∩ n2以下の集合| = Xect[n1][n2]
|n1以下の集合以外 ∩ n2以下の集合| = size[Tree2][n2] - Xect[n1][n2]
|n1以下の集合 ∩ n2以下の集合以外| = size[Tree1][n1] - Xect[n1][n2]
|n1以下の集合以外 ∩ n2以下の集合以外| = (N - size[Tree1][n1]) - (size[Tree2][n2] - Xect[n1][n2])

n1以下以外  n2以下以外
 0 1 2      2 3 
n1以下     n2以下
 3 4        0 1 4

のとき Xect[n1][n2] = |{4}| = 1
n1以下以外 ∩ n2以下 は?
→ 0 1 4 のうち 4 は Xect に入ってるので n1 以下にあるので "n1以下以外 ∩ n2以下" には含まれない。
→ それ以外の 0 1 は n1 以下にはないはずなので n1 以下以外にあるはず→つまり n1以下以外 ∩ n2以下 に含まれる
なので size[Tree2][n2] - Xect[n1][n2]
  • まずこれが思いつかんのだなこれが。
  • size は dfs で求まる

■ ポイント2

  • Xect も size みたいに葉→根に足していって求められる。
  • まず初期状態として、n1 n2 に対して {n1}の頂点ラベル集合 ∩ {n2}の頂点ラベル集合 = XectNodeNode[n1][n2] を考える。
  • これは同じかどうかなので XectNodeNode[n1][n2] = n1==n2
  • n1以下の頂点ラベル集合 ∩ {n2}の頂点ラベル集合 = XectTreeNode[n1][n2] を求めるために Tree1 を dfs する。
  • XectTreeNode ← XectNodeNode として
  • 帰りがけ順に XectTreeNode[node][i] += XectTreeNode[child][i] for i in [0, N), Tree1 に node-childの辺がある
  • 次に Tree2 視点にするために XectNodeTree ← XectTreeNode の転置 として
  • n1以下の頂点ラベル集合 ∩ n2以下の頂点ラベル集合 = Xect を求めるために Tree2 を dfs
  • Xect ← XectNodeTree としておいて
  • 帰りがけ順に Xect[node][i] += Xect[child][i] for i in [0, N), Tree2 に node-childの辺がある
  • 最後、すべての辺に対してその辺が分断するノードの片方をもれなく列挙するとこも微妙に悩ましいが、
  • 0 を根としたのだから 0 以外の頂点は必ず親を持つ
  • → 0 以外の頂点 i すべてについて i とその親を結ぶ辺を列挙すれば MECE になるので頂点 [1, N)x[1, N) を全部見ればよい。
  • 全体で O(N^2)
  • accepted in practice room
  • ふむふむほうほう
  • ちなみに tourist さんは 13 分 30 秒で解いています。( ﾟдﾟ)
// 理解した後に書いたコード　（ほぼそのままですね
class TreesAnalysis {
public:
	void dfs(int t, int idx, int prev, vector<VVI>& g, VVI& size, VVI& xect) {
		int N = xect.size();
		size[t][idx]=1;
		REP(i, g[t][idx].size()) {
			int ci=g[t][idx][i];
			if(ci==prev) continue;
			dfs(t, ci, idx, g, size, xect);
			size[t][idx]+=size[t][ci];
			REP(j, N) xect[idx][j]+=xect[ci][j];
		}
	}
	long long treeSimilarity(vector <int> T1, vector <int> T2) {
		int N=T1.size()+1;
		vector<VVI> g(2, VVI(N));
		VVI size(2, VI(N));
		VVI xect(N, VI(N));
		REP(t, 2) REP(i, N-1) {
			int j=(t==0?T1:T2)[i];
			g[t][i].PB(j);
			g[t][j].PB(i);
		}
		REP(i, N) xect[i][i]=1;
		REP(t, 2) {
			dfs(t, 0, -1, g, size, xect);
			REP(i, N) RANGE(j, i+1, N) swap(xect[i][j], xect[j][i]);
		}
		ll ans = 0;
		RANGE(i, 1, N) RANGE(j, 1, N) {
			int x=xect[i][j];
			int a=size[0][i];
			int b=size[1][j];
			ll add = max(x, max(a-x, max(b-x, N-a-(b-x))));
			ans += add*add;
		}
		return ans;
	}
};
コメント
 |