Quiz
https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c
AC code
https://atcoder.jp/contests/tenka1-2018-beginner/submissions/13108762
解説
- 解説の通り、a1 <= a2 <= a3 という単調増加の形はない
- a2を除去しても得られる得点は変わらないため
- それを考慮すると、最適に出来上がった数列はギザギザになる
- ギザギザの形が決まれば、絶対値記号が外れる
- 係数一覧が決まるので、値の大きいaを、大きい係数に対応させればいい
学び
形が決まれば絶対値が外れる
code抜粋
// 係数生成 VI generate_coefficient(ll N){ VI C; if(N%2==0){ C.push_back(1); C.push_back(-1); rep(i, (N-2)/2){ C.push_back(-2); C.push_back(2); } } else{ C.push_back(1); C.push_back(1); ll rest = N-2; ll plus = rest/2; ll minus = rest-plus; rep(i,plus) C.push_back(2); rep(i,minus) C.push_back(-2); } return C; } // 大きい係数に大きい値を当てる ll f(VI A, VI C){ RSORT(A); RSORT(C); ll sum=0; rep(i, A.size()){ sum += A[i] * C[i]; } return sum; } int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N; cin>>N; VI A(N); rep(i, N) cin >> A[i]; if(N==2){ ll diff = abs(A[0]-A[1]); p(diff); return 0; } VI C = generate_coefficient(N); ll ans0 = f(A, C); // 係数反転 rep(i,N) C[i] *= -1; ll ans1 = f(A, C); ll ma = max(ans0, ans1); p(ma); return 0; }