yukicoder : No.2157 崖

これも割と典型な気はする。
https://yukicoder.me/problems/no/2157

問題

N要素の整数列Aを作りたい。
各要素に用いることのできる値の一覧がそれぞれ与えられている。

この時、Aを広義単調増加となるようにし、また隣接要素の最大値を最小化したい。
可能なら、隣接要素の最大値の最小値を求めよ。

解法

隣接要素の最大値の最小値を二分探索する。
f(i,m) := Aのi要素目まで決めたとき、m番目の候補を取った場合に、そこまでの数列を条件を満たすように構成可能かどうか
というテーブルを考える。
f(N,*)の中に真となるものがあれば、条件を満たすことになる。

f(i,*)からf(i+1,*)を埋めて行こう。
各要素の候補を事前にソートしておけば、尺取り法の要領で処理できる。

int N,M;
int D[1515][1515];

int ok(int v) {
	vector<int> F(M,1);
	int i;
	FOR(i,N-1) {
		vector<int> G;
		int num=0;
		int j,L,R;
		for(j=0,L=R=0;j<M;j++) {
			while(R<M&&D[i][R]<=D[i+1][j]) num+=F[R++];
			while(L<M&&D[i][L]+v<D[i+1][j]) num-=F[L++];
			G.push_back(num>0);
		}
		
		swap(F,G);
	}
	
	return count(ALL(F),1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(y,N) {
		FOR(x,M) cin>>D[y][x];
		sort(D[y],D[y]+M);
	}
	ll ret=(1LL<<30)-1;
	if(ok(ret)==0) {
		cout<<-1<<endl;
	}
	else {
		for(i=29;i>=0;i--) if(ok(ret-(1<<i))) ret-=1<<i;
		cout<<ret<<endl;
	}
}

まとめ

考察はそこまで重くないね。