kmjp's blog

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

TopCoder SRM 654 Div1 Medium SuccessiveSubtraction2

450ptというけど結構手間取った。
http://community.topcoder.com/stat?c=problem_statement&pm=13699

問題

Div2 Hardと同じ問題。
N要素の整数列A[i]に対し、 A_0 - A_1 - A_2 - ... - A_{N-1}という数式を考える。
ここで、最大2組括弧をつけることで、式の結果を変えることができる。

ここでQ個のクエリ(P[i],V[i])が与えられる。
各クエリは、Aを1か所更新するもので、A[P[i]]=V[i]に置き換える。
各クエリ実行後のA[i]に対し、適切に括弧を加えたときの上記式の最大値をそれぞれ答えよ。

解法

前処理をした後、クエリ毎にデータ構造を少しずつ更新していく…かと思ったら、そんな必要はない。
前のクエリの結果を利用しなくても、クエリ1回あたりO(N)で処理でき、全体でO(N*Q)で処理できる。
よって以下、値の更新クエリの事は無視して、A[i]に括弧を加えて最大化することを考える。

括弧をどうつけても、A[0]は常に加算でA[1]は常に減算である。
ただしA[2]~A[N-1]に関しては、括弧をつけないと減算だが括弧をつけると加算にすることができる。
加算に出来るのは、連続した部分列最大2つである。
A[2]~A[N-1]を2つに分け、前半で1回以下、後半で1回以下加算列を含むときの最大値を求める。

例えば、A[2]~A[x]までのうち括弧を最大1組つける(=加算列を1つまで作る)事ができるとき、A[2]~A[x]までを加算/減算した値L[x]を最大化することを考える。
これは状態として以下の3つを考え、DPしていけば良い。

  1. まだ加算列が始まっていない(加算列を始めることができる)
  2. 加算列の途中である。
  3. 既に加算列は使い切った。

同様に、逆順にA[N-1]からA[y]まで括弧を最大1組つけたときの加算/減算した値R[y]を最大化するようDPする。

後は2≦i≦N-1に対しA[0]-A[1]+max(L[i]+[i])を答えればよい。
L,R及び最後の最大値の計算はいずれもO(N)である。

class SuccessiveSubtraction2 {
	public:
	int dodo(vector<int>& A) {
		int i,N=A.size()-2;
		int L[2020][3]={}, R[2020][3]={};
		FOR(i,N) {
			L[i+1][0]=L[i][0]-A[i+2];
			L[i+1][1]=max(L[i][0]+A[i+2],L[i][1]+A[i+2]);
			L[i+1][2]=max(L[i][1]-A[i+2],L[i][2]-A[i+2]);
		}
		for(i=N-1;i>=0;i--) {
			R[i+1][0]=R[i+2][0]-A[i+2];
			R[i+1][1]=max(R[i+2][0]+A[i+2],R[i+2][1]+A[i+2]);
			R[i+1][2]=max(R[i+2][1]-A[i+2],R[i+2][2]-A[i+2]);
		}
		int ret = max(L[N][0],max(L[N][1],L[N][2]));
		FOR(i,N) ret=max(ret,max(L[i][2],L[i][1])+max(R[i+1][1],R[i+1][2]));
		return A[0]-A[1]+ret;
	}
	
	vector <int> calc(vector <int> a, vector <int> p, vector <int> v) {
		int i;
		if(a.size()==1) a.push_back(0);
		
		vector<int> r;
		FOR(i,p.size()) {
			a[p[i]]=v[i];
			r.push_back(dodo(a));
		}
		return r;
	}
}

まとめ

最初は符号を反転する箇所をMinimum Range Sum Queryで求めようと無駄に色々やってしまった。