atcoder ABC 100 D - Patisserie ABC

問題

解法

公式解説が詳しいのでそこに書いてある通り。

https://img.atcoder.jp/abc100/editorial.pdf

$ x,y,z $ の3要素の正方向と負方向の組み合わせは $ 2 ^ 3 $ 通り。それぞれの組み合わせで $ x,y,z $ の合計が大きいものから $ M $ 個を取って合計が一番大きいものが答えとなる。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
using ll = long long;

int main() {
  int n,m;
  cin >> n >> m;
  ll x[n],y[n],z[n];
  REP(i,n) cin >> x[i] >> y[i] >> z[i];

  ll sum[1<<3][n],ans = 0;

  for (int bit = 0; bit < (1<<3); bit++) { // bit全探索
    REP(i,n) {
      sum[bit][i] = 0;
      // bitが立っているところは正方向、立ってなければ負方向
      sum[bit][i] += (bit >> 0 & 1) ? x[i] : -x[i];
      sum[bit][i] += (bit >> 1 & 1) ? y[i] : -y[i];
      sum[bit][i] += (bit >> 2 & 1) ? z[i] : -z[i];
    }

    sort(sum[bit], sum[bit]+n, greater<ll>()); // 降順ソート
    ll tmp = 0;
    REP(i,m) tmp += sum[bit][i]; // 大きいものからM個を合計する
    if (ans < tmp) ans = tmp;
  }

  cout << ans << endl;
}

雑感

貪欲法的なアプローチ
正/負方向を8通り決め打ちして考える、というのを思いつくのが難しい