Codeforces ECR #077 : D. A Game with Traps

問題文が長め。
http://codeforces.com/contest/1260/problem/D

問題

スタートからゴールまで途中Nマスを進んでいくことを考える。
その際、プレイヤーと軍を進めていく。
移動手順は以下のいずれかを取れる。いずれも時間は1かかる。

• プレイヤーが単独で隣接マスに移動する
• プレイヤーと軍が同じマスにいるとき、同時に両者が同じ隣接マスに移動する

軍の兵士にはそれぞれスキルが設定されている。
その際、途中いくつかのトラップがある。
トラップのあるマスは、トラップの危険度未満のスキルの兵士はそのままでは通行できない。
トラップはその先のマスに対応する解除マスがあるので、プレイヤーがそのマスに単独で移動し、トラップを解除すればスキルを問わず移動可能となる。

時刻T以内に最終マスに連れていける兵士は何人か。

解法

兵士のスキルの下限を二分探索することを考える。
そうすると解除しないといけないトラップが定まるので、あとは移動にかかる時間を求めればよい。
とはいえどん欲に解除しないといけないトラップがあれば、適宜プレイヤーが対応マスまで進んで解除して戻る、でよい。
その途中で他のトラップの解除マスがあればついでに解除すればよいし、あえて2つ以上先の解除マスまで先にたどる必要はない（それで時間が得することはない）

int M,N,K,T;
int A[202020];
int L[202020],R[202020],D[202020];

int ok(int v) {
	if(v>M) return 0;
	int S=A[v-1];
	vector<pair<int,int>> V;
	int i;
	FOR(i,K) if(D[i]>S) V.push_back({L[i],R[i]});
	sort(ALL(V));
	int ret=N+1;
	int PL=0,PR=0;
	FORR(v,V) {
		if(v.first<=PR) {
			PR=max(PR,v.second);
		}
		else {
			if(PL) ret+=(PR-PL+1)*2;
			PL=v.first;
			PR=v.second;
		}
	}
	if(PL) ret+=(PR-PL+1)*2;
	return ret<=T;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M>>N>>K>>T;
	FOR(i,M) cin>>A[i];
	sort(A,A+M);
	reverse(A,A+M);
	FOR(i,K) cin>>L[i]>>R[i]>>D[i];
	
	int ret=0;
	for(i=20;i>=0;i--) if(ok(ret+(1<<i))) ret+=1<<i;
	
	cout<<ret<<endl;
}

まとめ

どういう問題設定だったらもっと問題文がすっきりするんだろうな。