kmjp's blog

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

101 Hack 47 : D. Watson and DAG

Cよりラクでした。
https://www.hackerrank.com/contests/101hack47/challenges/watson-and-dag

問題

DAGに対するトポロジカルソートを考える。
ここで、パラメータkに応じてソートの動きが変わるものとする。

通常、トポロジカルソートでは未処理の頂点からの入次数が0の頂点を1つ選び、取り除くということを行う。
この際、候補となる頂点群Sのうち、頂点番号が小さい方からmin(k,|S|)番のものを選ぶとする。

T(k)を
T(k) := パラメータkによりグラフをトポロジカルソートしたときの取り除いた頂点番号列
と定義する。
 \sum_i \sum_j LCP(T(i),T(j))を求めよ。

解法

トポロジカルソートの過程で、Sからの頂点の選び方を考える。
k=1~(|S|-1)の場合、それぞれSから異なる頂点を選ぶので、以後それらは他のパラメータとのLCPを増加させない。
一方、k≧|S|となるkに対しては、Sから同じ頂点(最大の番号のもの)を選ぶので、それらはLCPが1増加する。
また、以後の処理において、k=1~(|S|-1)はすでにprefixが不一致となるので、以後k≧|S|のケースのみ考え、トポロジカルソートを継続すればよい。
prefixの不一致が生じる段階で、解にそこまで生じたprefixの一致分を加算しよう。

int N,M;
vector<int> E[505050];
ll ret;
int in[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x].push_back(y);
		in[y]++;
	}
	set<int> S;
	FOR(i,N) if(in[i]==0) S.insert(i);
	ret = 1LL*N*N;
	int mi=1;
	int step=0;
	while(S.size()) {
		while(mi<S.size()) ret += 2LL*step * (N-mi), mi++;
		step++;
		x = *S.rbegin();
		S.erase(x);
		FORR(r,E[x]) if(--in[r]==0) S.insert(r);
	}
	while(mi<N) ret += 2LL*step * (N-mi), mi++;
	cout<<ret<<endl;
	
}

まとめ

字で書くとややこしいけど、コードは単純。