kmjp's blog

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

Codeforces #553 Div2 E. Number of Components

GWの有志コンとかABC問題増とかGCJとかで5月は問題が多くて、何気にCodeforcesの記事は1か月以上空いてしまった。
https://codeforces.com/contest/1151/problem/E

問題

N頂点の無向グラフを考える。
i番と(i+1)番の頂点が辺で接続されている。

各頂点iには値A[i]が設定されており、1~Nのいずれかの値を取る。

f(L,R)を、値がL以上R以下の頂点だけからなる部分グラフの連結頂点数とする。
1≦L≦R≦Nとなる(L,R)のすべての組み合わせにおけるf(L,R)の総和を求めよ。

解法

各連結成分の最初の番号となる頂点を数え上げることを考える。
隣接要素(A[i],A[i+1])に対し、L,Rの取り方のうち、前者を含まず後者を含むケースを数えて足していけばよい。

int N;
ll A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	ll ret=0;
	ret+=A[0]*(N-A[0]+1);
	for(i=1;i<N;i++) {
		if(A[i-1]<A[i]) {
			ret+=(A[i]-A[i-1])*(N-A[i]+1);
		}
		if(A[i-1]>A[i]) {
			ret+=A[i]*(A[i-1]-1-A[i]+1);
		}
	}
	cout<<ret<<endl;
}

まとめ

Div2とはいえ2250ptにしては簡単な問題。
とはいえ自分も本番15分かかってるからちょっとは迷ったようだ。