Cよりラクでした。
https://www.hackerrank.com/contests/101hack47/challenges/watson-and-dag
問題
DAGに対するトポロジカルソートを考える。
ここで、パラメータkに応じてソートの動きが変わるものとする。
通常、トポロジカルソートでは未処理の頂点からの入次数が0の頂点を1つ選び、取り除くということを行う。
この際、候補となる頂点群Sのうち、頂点番号が小さい方からmin(k,|S|)番のものを選ぶとする。
T(k)を
T(k) := パラメータkによりグラフをトポロジカルソートしたときの取り除いた頂点番号列
と定義する。
を求めよ。
解法
トポロジカルソートの過程で、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; }
まとめ
字で書くとややこしいけど、コードは単純。