yukicoder : No.2840 RGB Plates

その言い換えに気付けなかった。
https://yukicoder.me/problems/no/2840

問題

N要素の整数列Aが与えられるので、これを3つの空でない列に分割したい。
2つ目と3つ目の数列の総和が一致するようにしたとき、1つ目の数列の総和の最大値を求めよ。

解法

以下を考える。
f(n,s) := Aのn要素目までのうち、いくつかを選び、sととなる組み合わせが何通りあるか
このうち、
f(N,s)が2以上となる最小のsを考える。
この時、この2通りは同じ値を重複して使っていないことがわかる。
もし重複する値wを使っているなら、f(N,s-w)も2以上になるためである。
よって、その用なsを満たす数列2通りを、2つ目と3つ目の数列に割り当てることで、sum(A)-2sが解となる。

考えるsの上限をKとすると、鳩ノ巣原理よりNが大きいほどsが小さいところで2以上になるはずなので、KはおよそNに反比例かつAの最大値に比例する形で定めてよい。
そうすると、O(Nmax(A))ぐらいになる。

int N;
int A[3030];
int K;

int from[111010];
int to[111010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	if(N<=20) K=100000;
	else if(N<=200) K=50000;
	else K=10000;

	int ret=-1;
	int S=0;
	from[0]=1;
	FOR(i,N) {
		cin>>A[i];
		S+=A[i];
		for(j=K;j>=0;j--) from[j+A[i]]=min(2,from[j+A[i]]+from[j]);
	}
	
	FOR(i,K+1) if(from[i]>=2) ret=max(ret,S-i*2);
	if(ret==0) ret=-1;
	cout<<ret<<endl;
	
}

まとめ

探索範囲をここまで絞れるってことにさっとたどり着けなかった。