🎃

Tenka1 Programmer Beginner Contest | C - Align

2020/12/10に公開

問題

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

考えたこと

最適な解の数列をBとし、i番目の数値をb_iとする。
このとき数列に、b_{i-1} < b_i < b_{i+1}b_{i-1} > b_i > b_{i+1}となるb_iは存在しない。
もし存在するとしたら、b_iを末尾などに移動させることにより、先程の三項の差より合計が大きくなるからである。

最適な形としては以下の2パターンになる。

b_{0} > b_{1} < b_2 > ... \tag{1}
b_{0} < b_{1} > b_2 < ... \tag{2}

ここで、(1)のとき、b_iの差の合計は以下のようになる。

b_0 - 2b_1 + 2b_2 - ...

末尾は奇数か偶数かで変わってくるが、b_iが-1のときb_{i+1}が追加されるとb_i = -2, b_{i+1} = 1となるここと、b_iが1のときb_{i+1}が追加されるとb_i = 2, b_{i+1} = -1となるこことを利用して配列にいれてやると計算しやすい。

ここで先程のb_iの係数配列に入れてソートし、ソートされたA_iとかけあわせると(1)のときの差の合計の最大値が求まる。
(2)のときも同じようにして解き、(1)と(2)の最大値を求めれば答えとなる。

コード

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

ll solve(vector<ll> &a, ll b0, ll b1) {
  const int n = a.size();
  vector<ll> b(n);
  // p1 > p2 < p3 > p4 ...
  b[0] = b0, b[1] = b1;
  for (int i = 1; i < n - 1; i++) {
    if (b[i] == -1) {
      b[i] = -2;
      b[i + 1] = 1;
    } else {
      b[i] = 2;
      b[i + 1] = -1;
    }
  }
  sort(b.begin(), b.end());
  ll v = 0;
  for (int i = 0; i < n; i++) {
    v += a[i] * b[i];
  }
  return v;
}

int main() {
  ll n;
  cin >> n;
  vector<ll> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  // 係数を計算する
  vector<ll> b(n);

  ll mx = 0;
  // p1 > p2 < p3 > p4 ...
  mx = max(mx, solve(a, 1, -1));
  // p1 < p2 > p3 < p4...
  mx = max(mx, solve(a, -1, 1));

  cout << mx << endl;
}

参考

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

Discussion