Manthan Codefest 19 : E. Let Them Slide

これはまぁまぁレート増えて良かった。
https://codeforces.com/contest/1208/problem/E

問題

W列H行のグリッドがある。
各行rに対し、L要素の数列A[r]が与えられる。
各行において、グリッド中連続するL列のマスに、この数列を当てはめるものとする。

各列の値の和の最大値を求めよ。

解法

各行について、各セルには数列の区間のうちの最大値が設定できることになる。
LがWの半分以上であるような大きな数列に対しては、最大値ウインドウなど使いつつ愚直に当てはめる値を求めていけばよい。

Lが小さい場合、列の真ん中のほとんどの部分には数列の最大値を設定できる。
愚直に行うとTLEするので、階差数列を書き込んでおき、最後に累積和を取るようにするとよい。

int N,W;
vector<int> V;
ll S[1010101];
ll QS[1010101];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&W);
	FOR(i,N) {
		scanf("%d",&x);
		V.resize(x);
		int ma=0;
		FOR(j,x) {
			scanf("%d",&V[j]);
			ma=max(ma,V[j]);
		}
		if(V.size()==W) {
			FOR(j,W) S[j]+=V[j];
		}
		else if(V.size()*2>W) {
			int d=W-V.size();
			deque<pair<int,int>> Q;
			Q.push_back({-1,0});
			V.push_back(0);
			FOR(j,W) {
				while(Q.size() && Q.front().first<j-d) Q.pop_front();
				if(j<V.size()) {
					while(Q.size() && Q.back().second<=V[j]) Q.pop_back();
					Q.push_back({j,V[j]});
				}
				S[j]+=Q.front().second;
			}
		}
		else {
			QS[V.size()]+=ma;
			QS[W-V.size()]-=ma;
			int ma=0;
			FOR(j,V.size()) {
				ma=max(ma,V[j]);
				S[j]+=ma;
			}
			ma=0;
			FOR(j,V.size()) {
				ma=max(ma,V[V.size()-1-j]);
				S[W-1-j]+=ma;
			}
		}
	}
	
	FOR(i,W) {
		if(i) QS[i]+=QS[i-1];
		cout<<(S[i]+QS[i])<<" ";
	}
	cout<<endl;
	
}

まとめ

これ去年の8月か…。