kmjp's blog

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

Wunder Fund Round 2016 : F. Double Knapsack

これは思いつかんな。
http://codeforces.com/contest/618/problem/F

問題

1~Nの数値がN個で構成される2つのmultiset A,Bがある。
それぞれの部分集合のうち総和が等しくなるものを1組生成せよ。

解法

Editorialを見て回答。鳩ノ巣原理を用いる。
Aの先頭i要素の総和をa[i]、Bの先頭j要素の総和をb[j]とする。
尺取法の要領で、a[i]に対してa[i]を超えない最大のb[j]を求めよう。

  • a[i]==b[j]なら、Aの先頭i要素とBの先頭j要素がこの問題の解。
  • そうでない場合、a[i]-b[j]=x[i]と置く。
    • x[i]は1~(N-1)のいずれかだが、iは0~(N-1)のN通りあるので、xが一致するような2つの値i,i'が存在する。
    • a[i]-b[j]=a[i']-b[j']とすると、Aの(i+1)~i'要素及びBの(j+1)~j'要素が解。
int N;
int A[1010100];
int B[1010100];
int T[1010100];
ll AS[1010100];
ll BS[1010100];
int bask[1010100];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i], AS[i+1]=AS[i]+A[i];
	FOR(i,N) cin>>B[i], BS[i+1]=BS[i]+B[i];
	
	MINUS(bask);
	bask[0]=0;
	y=0;
	FOR(i,N) {
		while(y<N&&BS[y+1]<=AS[i+1]) y++;
		T[i]=y;
		int dif=AS[i+1]-BS[y];
		
		if(bask[dif]==-1) bask[dif]=i+1;
		else {
			_P("%d\n",i-(bask[dif]-1));
			for(x=bask[dif];x<=i;x++) _P("%d ",x+1);
			_P("\n");
			_P("%d\n",y-T[bask[dif]-1]);
			for(x=T[bask[dif]-1];x<y;x++) _P("%d ",x+1);
			_P("\n");
			return;
		}
	}
	
}

まとめ

鳩ノ巣原理に気づけば非常に単純な問題。まぁ簡単に気づけないけど…。