tenka1_2018_c ~形が決まれば絶対値が外れる~

Quiz

f:id:peroon:20200511105954p:plain

https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c

AC code

https://atcoder.jp/contests/tenka1-2018-beginner/submissions/13108762

解説

f:id:peroon:20200511105827p:plain

  • 解説の通り、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;
}