Codeforces #620 Div2 F2. Animal Observation (hard version)

この回はEまで妙に簡単。
https://codeforces.com/contest/1304/problem/F2

問題

N*Mの行列が与えられる。
またパラメータKが与えられる。

各行rに対し、任意の列cを指定し、2*Kの矩形区間(r,c)-(r+1,c+K-1)をカバーできるとする。
(最終行に対しては1*Kのみ)
1個以上の区間でカバーされた領域の行列の値の総和の最大値を求めよ。

解法

f(r,c) := 1行目から順に矩形の配置を選択したとき、r行目で左上マスにcを指定したときのカバー領域の値の総和の最大値
とする。f(r,*)からf(r+1,*)を求めよう。

f(r,c)を、区間加算・区間最大値可能なSegTreeに乗せよう。
f(r+1,c')を求めるときはf(r,c)に(r+1,c')を左上マスに指定したときの増分の和の最大値を取りたいわけだが、例えば(r,c)-(r+1,c+K-1)と(r+1,c')-(r+2,c'+K-1)に重複があると、その分を差し引かなければならない。
そこで、c'を端から順に処理しつつ、重なりが生じる分の変化をSegTreeの区間加算でf(r,c)の範囲から増減することで対応しよう。

int H,W,K;
int A[51][20202];
ll S[51][20202];

ll dp[20202];

static ll const def=0;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
		FOR(i,NV) val[i+NV]=ma[i+NV]=def;
		for(i=NV-1;i>=1;i--) ma[i]=max(ma[2*i],ma[2*i+1]);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return ma[k];
		return val[k]+max(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+max(ma[k*2],ma[k*2+1]);
		}
	}
};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	FOR(y,H) {
		FOR(x,W) {
			cin>>A[y][x];
			S[y][x+1]=S[y][x]+A[y][x];
		}
	}
	for(x=0;x+K<=W;x++) dp[x]=S[0][x+K]-S[0][x]+S[1][x+K]-S[1][x];
	for(y=1;y<H;y++) {
		SegTree_3<ll,1<<16> st;
		for(x=0;x+K<=W;x++) st.update(x,x+1,dp[x]);
		FOR(x,K) st.update(x-K+1,x+1,-A[y][x]);
		for(x=0;x+K<=W;x++) {
			dp[x]=S[y][x+K]-S[y][x]+S[y+1][x+K]-S[y+1][x]+st.getval(0,W);
			st.update(x-K+1,x+1,A[y][x]);
			st.update(x+1,x+K+1,-A[y][x+K]);
		}
	}
	
	ll ret=0;
	FOR(x,W) ret=max(ret,dp[x]);
	cout<<ret<<endl;
	
		
	
}

まとめ

まだまだ先は遠い…。