kmjp's blog

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

Codeforces #333 Div1 B. Lipshitz Sequence

考察に結構手間取ったうえ、TLEを繰り返した。
http://codeforces.com/contest/601/problem/B

問題

数列H[1..n]に対し、リプシッツ定数L(H)は以下のように定義される。

  • 1要素ならL(H)=0
  • 2要素以上ならL(H)= max(ceil*1 (i>j)

ここでN要素の数列A[i]が与えられる。
また、この数列に対しQ個のクエリが与えられる。
各クエリは区間[L[j],R[j]]からなる。A[L[j]..R[j]]の全連続部分列に対し、リプシッツ定数の和を求めよ。

解法

L(H)の計算式に登場するi,jは、結局j=i+1しかありえない。
ceil内の値は結局数列内の2要素に関する傾きの絶対値を表すものなので、|H[i+1]-H[i]|が最大となるiが結局最大となる。
よってL(H) = max(|H[i+1]-H[i]|)となる。

A[x..y]の全連続部分列に対する、リプシッツ定数の和を考える。
A[x..y]において、L(A[x..y])=|A[i+1]-A[i]|、すなわち隣接2要素の差の絶対値が最大となる要素をi番とする。
A[x..y]の連続部分列のうち、A[i..(i+1)]を含む(i-x+1)*(y-i)通りはリプシッツ定数の値が|A[i+1]-A[i]|なる。
あとは同様にA[i..(i+1)]を含まない部分列、すなわちA[x..i]及びA[(i+1)..y]の連続部分列ごとに傾きが最大となる要素を求めていけば良い。

上記考え方を整理する。
まずクエリの事は忘れて、A[0..(N-1)]全体に対し、全連続部分列に対するリプシッツ定数の和を求めてみよう。
まず|A[i+1]-A[i]|を降順ソートし、対応するiごとに順に処理していく。
初期状態はA[0..(N-1)]を対象とし、上記のとおりA[i..(i+1)]を含む部分列A[x..y]に対して、上記(i-x+1)*(y-i)*|A[i+1]-A[i]|を答えに加算し、残った部分列をA[x..i]、A[(i+1)..y]に分解していく。

上記では初期状態をA[0..(N-1)]とし、iごとにそれを含むA[x..y]を求めていった。
クエリ毎の処理においては初期状態がA[L[i]..R[i]]なので、上記各部分列を分解していく過程で、A[L[i]..R[i]]にも含まれる部分だけを対象とすればよい。
A[i..(i+1)]を含む部分列を求める処理は、クエリ毎に毎回二分探索したりするとTLEするので1回だけ探索するようにしよう。

int N,Q;
int A[101010];
pair<int,int> P[101010];
int L[101],R[101];
ll ret[101];
set<int> S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>A[i];
	
	FOR(i,N-1) P[i]={abs(A[i+1]-A[i]),i};
	sort(P,P+(N-1));
	reverse(P,P+(N-1));
	FOR(i,Q) {
		cin>>L[i]>>R[i];
		L[i]--,R[i]--;
	}
	S.insert(-1);
	S.insert(N-1);
	
	FOR(i,N-1) {
		x=P[i].second;
		auto it=S.lower_bound(x);
		int RR=*it;
		it--;
		int LL=1+(*it);
		
		FOR(j,Q) {
			ll NR=min(RR,R[j]);
			ll NL=max(LL,L[j]);
			
			if(NL<=x && x+1<=NR) {
				ll num=(x-NL+1)*(NR-x);
				ret[j]+=num*P[i].first;
			}
		}
		S.insert(x);
	}
	FOR(j,Q) cout<<ret[j]<<endl;
	
	
}

まとめ

考察ができればコードはそこまで難しくない。

*1:|H[j]-H[i]|)/(j-i