けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2942 Absum (RUPC 2019 day1-F)

難しくて、てんぷらたんが天才だった!!!!!!!
とにかくすごかった!!!!!
そしてすごく面白い問題だった!!!!!

問題へのリンク

問題概要

長さ  N の数列  A が与えられる。数列の 2 要素を選んで swap する操作を高々  M 回まで行うことができる。

操作を行ってできる数列の  \sum_{i = 0}^{N-1} |A_{i} - i| の最大値を求めよ。

制約

  •  2 \le N \le 10^{5}
  •  0 \le M \le N

M が無限なら

まず、

  •  |A_i - i| = (A_i - i) または  (i - A_i)

であることに注意すると、各  i に対して  A_i i のうちどちらがプラスでどちらがマイナスになるかを割り当てるような雰囲気の問題になる。

もし可能なら、 A_i i も全部ひっくるめて  2N 個の整数について大きい順に並べたときに、大きい順に  N 個がプラスになるような状態にしたい。これは  M が無限なら実は可能で、 A_i を降順に並べてあげると、例えばサンプル 3 について

+6, +5, +4, +3, -1, -0
-0, -1, -2, -3, +4, +5

という感じになる。1 行目に  A_i を、2 行目に  i を書いた。

現実には  M が有限なのでここまで理想的な状態にはできるとは限らないが、理想的な状態に持って行きたい。この問題に限らず、操作が  M 回までしか行えない問題について、まずは  M が無限大の場合について考えることは有益な気がする。

問題の swap 操作を、符号入替操作で言い換える

サンプル 3 の初期状態は

+1, -0, +3, +6, +5, -4
-0, +1, -2, -3, -4, +5

という感じになっている。ここで「-4」とかはできれば「+4」にしたいし、「+1」とかは別に「-1」でもいいような気持ちになる。

さて、ここでプラスのやつとマイナスのやつにそれぞれ分けてみる。

+6 +5 +5 +3 +1 +1

vs.

-4 -4 -3 -2 -0 -0

ここで、実は


 a -b とがあって、 a <  b であるとする。これらの符号をひっくり返して、 -a b の状態にしたい。

実は、それはある 1 回の swap 操作によって必ず実現できる


ということが言える。一応示してみる。

a と -b とが元々同じ index にあったとき (ある i が存在して a と b のうちどちらかが Ai でどちらかが i のとき)

そんなことは起こらない。なぜなら、それなら  -a +b になるはず。

それ以外のとき

ある index  i, j ( i \neq j) と、整数  c, d (c \le a <  b \le d) が存在して

  •  (A_i, i) から  (a, -c) が生じている
  •  (A_j, j) から  (d, -b) が生じている

という状態になっている。ここで  i j に対して swap 操作を行うと、

  •  (-a, b) (-c, d)
  •  (-a, d) (-c, b)

のいずれかが生じることになる。よく見ると、swap 前に比べて、 a b の符号が入れ替わっていることがわかる。

結局 swap 操作を言い換えると

以上から示せた。逆に swap 操作を任意に一つとって来たときに、「正の値の集合」と「負の値の集合」とにどんな影響を与え得るのかについても検討しておく。もしかしたら  a -b の符号を入れ替えるよりも良い swap 操作が存在するかもしれないからだ。

さて、任意の swap 操作は、「正の値の集合」と「負の値の集合」とになんら変化を与えないか、ある正の値  a とある負の値  -b に対し、それらをそれぞれ  -a b に変更するかのいずれかである、ということがすぐにわかる。

ここで必ずしも  a <  b であるとは限らないが、 a <  b なペアであれば必ず符号入替操作ができることが重要である。

以上をまとめると、問題が要求している swap 操作は、意味のあるものに限ると

  •  a -b とがあって、 a <  b であるとして、それらを  -a b の状態にする操作

に対応させることができた。

詰め

以上のことから、問題は、

+6 +5 +5 +3 +1 +1

vs.

-4 -4 -3 -2 -0 -0

のような初期状態から出発して、マイナス側の絶対値が大きいやつと、プラス側の絶対値が小さいやつとの符号入替操作を、最大  M 回行うことで、どれだけ総和を大きくできるかを問う問題だと言うことができる。

これは単純に、貪欲にやって行けば良い。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    int N, M; cin >> N >> M;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    long long res = 0;
    vector<long long> plus, minus;
    for (int i = 0; i < N; ++i) {
        res += abs(a[i] - i);
        if (a[i] >= i) plus.push_back(a[i]), minus.push_back(i);
        else plus.push_back(i), minus.push_back(a[i]);
    }
    sort(plus.begin(), plus.end());
    sort(minus.begin(), minus.end(), greater<long long>());

    for (int i = 0; i < M; ++i) {
        if (plus[i] < minus[i]) {
            res += (minus[i] - plus[i]) * 2;
        }
        else {
            break;
        }
    }
    cout << res << endl;
}