Google Code Jam 2022 Round 1A : B. Equal Sum

これまた変わったinteractive(adaptive?)
https://codingcompetitions.withgoogle.com/codejam/round/0000000000877ba5/0000000000aa8fc1

問題

1～10^9の範囲の200個の異なる整数が、総和が偶数となるように与えられる。
この時、200個中100個はこちらで値を決められる。

これらを2つのグループに分け、グループ内の和が等しくなるようにしたい。
両グループ内の整数の個数は等しくなくても良い。

解法

最初の100の中に、2^0、2^1、…、2^29を入れておこう。
あとは200個の中から大きい順に、「これをグループに入れても総和の半分以下をキープできる」というものをどん欲に取り込んでいく。

最初に入れた2^0、2^1、…、2^29のお陰で、総和が2^30未満の微調整が効くので他の170個の整数が何であれうまく2グループに分割できる。

int N;
ll A[201],B[101];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	ll S=0;
	FOR(i,N) {
		if(i<30) {
			A[i]=1<<i;
		}
		else {
			A[i]=(1<<29)+i;
		}
		cout<<A[i];
		S+=A[i];
		if(i<N-1) cout<<" ";
		else cout<<endl;
	}
	
	FOR(i,N) {
		cin>>A[i+N];
		S+=A[i+N];
	}
	S/=2;
	sort(A,A+2*N);
	vector<ll> R;
	for(i=2*N-1;i>=0;i--) if(S>=A[i]) {
		S-=A[i];
		R.push_back(A[i]);
	}
	FOR(i,R.size()) {
		cout<<R[i];
		if(i<R.size()-1) cout<<" ";
	}
	cout<<endl;
}

まとめ

色々考えるなぁ。