kmjp's blog

競技プログラミング参加記です

TopCoderOpen 2016 Round1B Hard SettingShield

証明できるのかな?
https://community.topcoder.com/stat?c=problem_statement&pm=14203

問題

N要素の整数列Pを考える。
同じく初期値0のN要素の整数列Aに数値を加算していき、各要素A[i]がP[i]以上となるようにしたい。

H種類の区間(L[i],R[i])が与えられる。
コストを1払うと、A[L[i]]~A[R[i]]を1加算できる。
また、コストをT払うと、Aの全要素を1加算できる。

各要素A[i]がP[i]以上となるようにする最小コストを求めよ。

解法

コストをT払ってAの全要素を1加算する回数に対し、総コストは下に凸になるらしい。
(残念ながら証明方法はわからず)

あとはAの全要素加算を定めたときのコストが簡単に求められれば、三分探索で解を求められる。
Aの各要素を先頭から見ていき、全要素加算してもまだP[i]から不足している箇所があれば、累積和のテクを用いつつiを含むもっとも末尾の遠い区間(L[j],R[j])に対し、不足分1加算を繰り返せばよい。

int P[101010];
int L[101010],R[101010];
int MR[101010];
int delta[101010];

class SettingShield {
	public:
	int N,H,T;
	
	ll calc(ll v) {
		int i;
		if(v<0) return 1LL<<60;
		ll w=v,cost=0;
		ZERO(delta);
		FOR(i,N) {
			w+=delta[i];
			if(w<P[i]) {
				if(MR[i]<i) return 1LL<<60;
				cost += P[i]-w;
				delta[MR[i]+1] -= P[i]-w;
				w = P[i];
			}
		}
		return cost + v*T;
	}
	
	long long getOptimalCost(int n, int h, int t, vector <int> val0, vector <int> a, vector <int> b, vector <int> m) {
		int i,j;
		N=n;
		H=h;
		T=t;
		P[0]=val0[0];
		for(i=1;i<N;i++) P[i]=(1LL*a[0]*P[i-1]+b[0]) % m[0];
		
		MINUS(MR);
		L[0]=val0[1];
		R[0]=val0[2];
		MR[L[0]]=R[0];
		for(i=1;i<H;i++) {
			L[i] = min(N-1LL,(1LL*a[1]*L[i-1]+b[1]) % m[1]);
			R[i] = min(N-1LL,L[i]+(1LL*a[2]*(R[i-1]-L[i-1])+b[2]) % m[2]);
			MR[L[i]]=max(MR[L[i]],R[i]);
		}
		for(i=1;i<N;i++) MR[i]=max(MR[i],MR[i-1]);
		
		
		ll ret=1LL<<60;
		int LL=0,RR=10000005;
		FOR(i,30) {
			int m1=(LL*2+RR)/3;
			int m2=(RR*2+LL)/3;
			ll v1=calc(m1);
			ll v2=calc(m2);
			if(v2>=1LL<<60) LL=m2;
			else if(v1<v2) RR=m2;
			else if(v1>v2) LL=m1;
			else LL=m1,RR=m2;
		}
		for(i=LL-10;i<=RR+10;i++) ret=min(ret,calc(i));
		return ret;
	}
}

まとめ

Codeforcesでは赤い人も証明がわからんと言っているな。

広告を非表示にする