Codeforces ECR #150 : E. Fill the Matrix

問題の理解に手間取るな。
https://codeforces.com/contest/1841/problem/E

問題

N*Nのグリッドがある。
整数列Aが与えられており、N列目は上からA[i]行目までのセルが黒く塗られている。

整数Mが与えられるので、白いマスのうちM個を選び1～Mを書き込むとする。
横の隣接マスが隣の値を書いているような隣接マスの対は何通りか。

解法

白マスがn個横に並んでいると、n個の値を書き込めば最大(n-1)個求める対を作れる。
よって、白マスが何マス並んでいるものが何個あるかを数え上げ、並びの大きい順にM個の値を埋めて行こう。
これはよくあるヒストグラムの横幅を列挙するタイプの問題で典型。

int T,N;
ll M,A[202020];
ll num[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		
		FOR(i,N+2) num[i]=0;
		vector<pair<int,int>> V;
		V.push_back({0,0});
		FOR(i,N) {
			cin>>x;
			x=N-x;
			while(V.back().first>x) {
				y=max(x,V[V.size()-2].first);
				num[i-V.back().second]+=V.back().first-y;
				
				if(x>V[V.size()-2].first) {
					V.back().first=x;
					break;
				}
				
				V.pop_back();
			}
			if(x>V.back().first) V.push_back({x,i});
		}
		while(V.size()>1) {
			num[N-V.back().second]+=V.back().first-V[V.size()-2].first;
			V.pop_back();
		}
		
		cin>>M;
		ll sum=0;
		for(i=N;i>=1;i--) {
			ll s=num[i]*i;
			if(M>=s) {
				sum+=(i-1)*num[i];
				M-=s;
			}
			else {
				sum+=M-(M+(i-1))/i;
				M=0;
			}
		}
		cout<<sum<<endl;
	}
}

まとめ

問題文に図が欲しいところ。