AtCoder AGC #015 : E - Mr.Aoki Incubator

Dよりこっち解いた方がよかったかも…。
http://agc015.contest.atcoder.jp/tasks/agc015_e

問題

N人の高橋君がおり、初期位置X[i]から速度V[i]で移動する。
初期状態でN人中何人か青木君を選ぶとする。
以後、N人が移動する際2人が同じ位置に来た瞬間、両者とも青木君になる。この動作は途中で青木君になった人にも生じる。

初期状態での青木君の選び方2^N通りのうち、最終的に全員が青木君になるケースは何通りあるかを求めよ。

解法

まず、N人を初期位置で昇順にソートする。
また、速度は大小の相対値のみ重要で絶対値はどうでもいいので、座標圧縮しておこう。

i番一人だけが青木君だったとすると、最終的に青木君になるのは手前にいる最大速度の人より遅く、前方にいる最小速度の人より早い人である。
手前の最大速度をL[i]、前方の最小速度をR[i]とすると速度が[R[i],L[i]]の人が対象となる。
重要なのは、L,Rの値を除けば人の位置は関係ないことである。またR,Lともにiとともに単調増加する。

よって、区間[R[i],L[i]]をいくつか選んで(座標圧縮後の)全区間[1,N]をカバーする方法を答えればよい。
f(i,x) := i番目の人まででで[0,x]をカバーする組み合わせ数
とすると
となる。
実際には配列を使いまわせば前者のsumは要らないし、後者のsumは累積和を適宜取りながら処理していけばよい。

int N;
pair<int,int> P[202020];
int V[202020],L[202020],R[202020];

ll dp[202020];
ll S[202020];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	map<int,int> M;
	cin>>N;
	FOR(i,N) {
		cin>>P[i].first>>P[i].second;
		M[P[i].second]=0;
	}
	sort(P,P+N);
	x=0;
	FORR(r,M) r.second=++x;
	FOR(i,N) {
		V[i]=M[P[i].second];
		R[i]=max(i?R[i-1]:V[i],V[i]);
	}
	for(i=N-1;i>=0;i--) {
		L[i]=min((i==N-1)?V[i]:L[i+1],V[i]);
	}
	
	dp[0]=S[0]=1;
	y=0;
	FOR(i,N) {
		while(y<R[i]) y++,(S[y]=S[y-1]+dp[y])%=mo;
		ll x=mo+S[R[i]]-((L[i]-2>=0)?S[L[i]-2]:0);
		(dp[R[i]]+=x)%=mo;
		(S[R[i]]+=x)%=mo;
	}
	cout<<dp[N]<<endl;
}

まとめ

あーでも[L[i],R[i]]でカバーする問題と気づくまで手間取るのかな。