Codeforces #1064 : Div1 D. Path Split

今回解くのにかかった時間がB＞C＞Dだな…。
https://codeforces.com/contest/2165/problem/D

問題

整数列Dが与えられる。
これをいくつかの(元々不連続な要素を選んでも良くて)部分列に分割したとき、各部分列は隣接要素の差の絶対値が1となるようにしたい。
最小いくつの整数列に分割すればよいか。

解法

値の大きい順に見て行く。
各値は、左右が開いている(１小さい値が連なる余地がある)かどうかを定めていこう。

今A[i]=nをどうするか考えるとき、

• A[j]=n+1となるi＜jのうち、最小かつ左側が空いているものがあれば、A[i]の右にA[j]をつなげる。
• A[j]=n+1となるj＜iのうち、最大かつ右側が空いているものがあれば、A[i]の左にA[j]をつなげる。

という処理を貪欲にやっていこう。
つなげる先がない場合、新たな部分列を１個追加することになる。

int T,N,A[1<<20],mask[1<<20];
vector<int> P[2<<20];
set<int> L[2<<20],R[2<<20];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,2*N) L[i].clear(),R[i].clear(),P[i].clear();
		FOR(i,N) {
			cin>>A[i];
			A[i]--;
			mask[i]=3;
			L[A[i]].insert(i);
			R[A[i]].insert(i);
			P[A[i]].push_back(i);
		}
		int ret=N;
		for(i=2*N-1;i>=1;i--) {
			FORR(p,P[i]) {
				if(mask[p]&1) {
					auto it=R[i-1].lower_bound(p);
					if(it!=R[i-1].begin()) {
						x=*prev(it);
						ret--;
						mask[x]^=2;
						R[i-1].erase(prev(it));
					}
				}
			}
			reverse(ALL(P[i]));
			FORR(p,P[i]) {
				if(mask[p]&2) {
					auto it=L[i-1].lower_bound(p);
					if(it!=L[i-1].end()) {
						x=*it;
						ret--;
						mask[x]^=1;
						L[i-1].erase(it);
					}
				}
			}
		}
		cout<<ret<<endl;
	}
		
}

まとめ

DPを要素順でなく値順に見て行くやつ、以前ARCで解けなくて記憶に残ってたので、今回もすんなり行けた。