証明できるのかな?
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では赤い人も証明がわからんと言っているな。