AtCoder ABC 100 D - Patisserie ABC (水色, 400 点)

ABC 100 D - Patisserie ABC

問題概要

整数 3 つ組 (xi, yi, zi) が N 個与えられる。
このうちの M 個選んで、

(x の選んだ M 個の総和の絶対値) + (y の選んだ M 個の総和の絶対値) + (z の選んだ M 個の総和の絶対値)

が最大になるようにせよ。

制約

• 1 <= N <= 1000
• -10¹⁰ <= xi, yi, zi <= 10¹⁰

解法

一瞬部分和問題的な DP をしたくなるけれど、x, y, z の制約が 10⁹ とかなので無理そうだという感じになる。

絶対値をとるという操作は、「そのまま」と「-1 倍したもの」の大きい方を選ぶ操作に他ならない。したがって選んだ M 個の最適解は

• x についての M 個の総和の、「そのまま」or「-1 倍する」 の大きい方
• y についての M 個の総和の、「そのまま」or「-1 倍する」 の大きい方
• z についての M 個の総和の、「そのまま」or「-1 倍する」 の大きい方

を足した形になっている。

ここで、それぞれの「そのまま」or「-1 倍する」を決め打ちして例えば

• x については M 個の総和の、「そのまま」
• y については M 個の総和の、「-1 倍」
• z については M 個の総和の、「そのまま」

が最適解だったと仮定すると、最適解は

• x[i] - y[i] + z[i] が大きい順に M 個選んで足したもの

になる。同様に、x, y, z それぞれについての「そのまま」「-1 倍する」のパターンを 2³ = 8 通り試して、一番大きいものをとればよい。

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

int N, M;

int main() {
    cin >> N >> M;
    vector<long long> a[3];
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 3; ++j) {
            long long num; cin >> num;
            a[j].push_back(num);
        }
    }
    long long res = 0;
    for (int bit = 0; bit < (1<<3); ++bit) {
        vector<long long> b;
        for (int i = 0; i < N; ++i) {
            long long tmp = 0;
            for (int j = 0; j < 3; ++j) {
                if (bit & (1<<j)) tmp += a[j][i];
                else tmp -= a[j][i];
            }
            b.push_back(tmp);
        }
        sort(b.begin(), b.end(), greater<long long>());
        long long sum = 0;
        for (int i = 0; i < M; ++i) {
            sum += b[i];
        }
        res = max(res, sum);
    }
    cout << res << endl;
}