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分かかってるからちょっとは迷ったようだ。