kmjp's blog

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

Codeforces #353 Div2 E. Trains and Statistic

C,Dより簡単に解けた…。
http://codeforces.com/contest/675/problem/E

問題

N頂点からなる有向グラフを考える。
頂点iからは、(i+1)~A[i]の範囲の頂点に1手で移動できる。

頂点対(i,j)(i<j)に対して、R(i,j)をi→jに至る対象の辺の遷移回数とする。
R(i,j)の総和を求めよ。

解法

S(i) := R(i,j)の総和
とする。
iの大きい順にS(i)を求めていこう。

iから(i+1)~A[i]には1手で移動できる。よってR(i,i+1)~R(i,A[i])はいずれも1である。
1手で移動できないA[i]以降の範囲に移動したいときは、(i+1)~A[i]の間の頂点xのうち、A[x]が最大のところに遷移しよう。
これはx=(i+1)~Nとなるxに対し、(x,A[x])が昇順になるようにならべた配列やsetを管理し、二分探索を用いることで高速に求められる。

そのようなxが定まるとする。
S(i)は以下で求められる。

  • (i+1)~iは1手で移動するのでA[i]-iをS(i)に足しこむ。
  • (A[i]+1)以降の頂点への遷移は、初回xへ移動してその後はxから移動する場合と同じなのでS(x) + (N-A[i])
    • ただし、S(x)はxから(x+1)~A[i]に移動する分も足しこまれている。これらはそもそもiから1手で移動できるので、その文(A[i]-x)を引く。
int N;
int A[101010];
ll S[101010];
ll ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) cin>>A[i],A[i]--;
	A[N-1]=N;
	set<pair<int,int>> L;
	L.insert({N-1,N});
	
	for(i=N-2;i>=0;i--) {
		
		while(L.begin()->second<=A[i]) L.erase(L.begin());
		auto it=L.lower_bound({A[i]+1,0});
		it--;
		x=it->first;
		S[i]=A[i]-i+S[x]-(A[i]-x)+N-1-A[i];
		L.insert({i,A[i]});
		ret += S[i];
	}
	cout<<ret<<endl;
}

まとめ

DもEもコード短いし、結局Cに一番苦戦した。