AtCoder ARC #121 (NOMURA プログラミングコンテスト 2021) : D - 1 or 2

この言い換えパターン、頭の片隅に入れておこう。
https://atcoder.jp/contests/arc121/tasks/arc121_d

問題

N個の整数が与えられる。
これらを、1つまたは2つを1つの組とし、いくつかの組に分ける。
組内の値の総和について、最大値と最小値の差が最小となるように組を分けたとき、その値を求めよ。

解法

全要素を2つで組にする場合を考えると、大きいものと小さいものを順にペアにしていくのがよい。
あとは1つだけで組を成すものの扱いであるが、これらは0と組にすると考えればよい。
そこで、0～N個、0を追加した状態について、上記の通り組を実際に作って値を計算するとよい。

int N;
vector<ll> A;

ll hoge(vector<ll> V) {
	if(V.size()%2) return 1LL<<60;
	sort(ALL(V));
	ll ma=-1LL<<60;
	ll mi=1LL<<60;
	int i;
	FOR(i,V.size()/2) {
		ll a=V[i]+V[V.size()-1-i];
		ma=max(ma,a);
		mi=min(mi,a);
	}
	return ma-mi;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		A.push_back(x);
	}
	ll mi=1LL<<60;
	mi=min(mi,hoge(A));
	FOR(i,N) {
		A.push_back(0);
		mi=min(mi,hoge(A));
	}
	cout<<mi<<endl;
	
}

まとめ

このテクに気付けば非常に簡単な問題だった。
うーん。