ARC092E: Both Sides Merger

https://arc092.contest.atcoder.jp/tasks/arc092_c

こういう問題も冷静になればシンプルに書けるんやなって。

結局、要素番号が偶数のやつから好きにとるか、奇数のやつから好きにとるかをすればいいとわかります。
構成法ですが、
1.数列を後から見て、使うやつまで全て消す。
2.数列を前から見て、使うやつまで全て消す。
3.数列の3番目の要素を見て、使うのだったら2番目に対して操作を行い、そうでなかったら3番目に対して操作を行う。
という順番でやれば簡単だと思います。

すべてマイナスの場合だけ注意しましょう。そのときも一番大きいelementを使うとして、上の構成法でできます。

int N, M = 0;
int A[MAX_N];
bool B[MAX_N];
int L, R;
int ans[MAX_N];

void add(int v) {
	ans[M++] = v;
}

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	ll es = 0, os = 0; //even sum, odd sum
	bool ok = false;// is B[i] == true exists?
	ll mx = -linf; int at = -1; //mxv and where mxv is located
	for(int i = 0; i < N; i++) {
		if(A[i] >= 0) {
			B[i] = true;
			ok = true;
			if(i % 2 == 0) es += A[i];
			else os += A[i];
		}
		if(mx < A[i]) {
			mx = A[i];
			at = i;
		}
	}
	if(!ok) {
		es = at % 2 == 0 ? mx : -linf;
		os = at % 2 == 0 ? -linf : mx;
		B[at] = true;
	}
	if(es >= os) {
		L = 0; 
		R = (N - 1) % 2 == 0 ? N - 1 : N - 2;
	}
	else {
		L = 1;
		R = (N - 1) % 2 == 0 ? N - 2 : N - 1;
	}
	while(!B[L]) L += 2;
	while(!B[R]) R -= 2;
	rep(i, 0, N - 1 - R) add(N - 1 - i);
	rep(i, 0, L) add(0);
	for(int l = L; l < R; l += 2) {
		if(!B[l + 2]) add(2);
		else add(1);
	}

	cout << max(es, os) << "\n";
	cout << M << "\n";
	rep(i, 0, M) {
		cout << ans[i] + 1 << "\n";
	}
}