kmjp's blog

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

CSAcademy Round #26 : E. Critical Cells

これは定番っぽい。
https://csacademy.com/contest/round-26/#task/critical-cells

問題

N*Mの2次元グリッドがある。
左上のマスから右下のマスまで、右または下の隣接マスを通って移動したい。

グリッド中K個の特殊なマスの位置が与えられる。
それらのうち、できるだけ多くの特殊マスを通る経路を考える。
そのような経路のうち、経由する特殊マス数を最大化するために必ず通ることになるマスはいくつあるか。

解法

特殊マスを(行番号,列番号)でpairwiseに昇順ソートし、列番号だけを取り出した数列を考える。
あとはこの列番号のLISにおいて、必ず含まれる要素数を答える問題となる。

これはおそらく定番問題。
先頭に無限小、末尾に無限大の値を加えておくとラク。
まずは通常のLISの処理を行い、元数列の各要素がLIS中何番目に来うるかを求める。
次に元数列を逆順に辿り、各要素がLISに含まれるかどうかを判定する。
(数列の以降の要素に、自身の値以上の値であり、LISに含まれ、かつLIST中で自身の次の位置に来うるかどうか判定する)

こうすると、LISのx番目に来るような要素が何個ずつあるかわかるので、1個しかないようなものの数を数えればよい。

int K;
pair<int,int> P[101010];
int X[101010];
vector<int> VX;
int ID[101010];
int ok[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>x>>y>>K;
	
	FOR(i,K) cin>>P[i+1].first>>P[i+1].second;
	P[K+1]={(1<<30)-1,(1<<30)-1};
	K+=2;
	sort(P,P+K);
	
	vector<int> A(K+2,1<<30);
	vector<int> lowest(K+2,0);
	int ma=-1;
	FOR(i,K) {
		X[i]=P[i].second;
		ID[i]=lower_bound(ALL(A),X[i]+1)-A.begin();
		A[ID[i]]=X[i];
		ma=max(ma,A[ID[i]]);
	}
	
	for(i=K-1;i>=0;i--) {
		if(i==K-1 || lowest[ID[i]+1]>=X[i]) {
			ok[ID[i]]++;
			lowest[ID[i]]=max(lowest[ID[i]],X[i]);
		}
	}
	
	cout<<count(ok,ok+K+2,1)-2<<endl;
	
}

まとめ

定番っぽいけどちょっと手間取った。