ABC 100 D Snuke Numbers

D - Patisserie ABC

問題概要

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

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

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

制約

1 <= N <= 1000

• 10の10乗 <= xi, yi, zi <= 10の10乗

感想

まずはnext_permutationで回し、最初のM個を取る楽なやり方ができないかと考えたが、条件からしてどう考えても無理。
次に再帰関数を使って解くことを考えたが、それもTLEで上手く行かない。分かんない；；

WAコード

using namespace std;
 
long long N;
long long M;
 
long long saiki(vector<vector <long long>> a, vector<long long> A) {
 
	if (A.size() == M) {
		long long mcount = 0;
		for (long long i = 0; i < 3; i++) {
			long long count = 0;
			for (long long j : A) {
				count += a[j - 1][i];
			}
			mcount += abs(count);
		}
		return mcount;
	}
	long long max = 0;
	long long prev_last = (A.empty() ? 1 : A.back());
 
	for (long long i = prev_last; i < M + 1; i++) {
		A.push_back(i);
		long long num = saiki(a, A);
		if (max < num) {
			max = num;
		}
		A.pop_back();
	}
 
	return max;
}
 
 
 
int main() {
 
 
	cin >> N;
	cin >> M;
 
	vector<vector <long long>> a(N, vector<long long>(M));
 
	for (long long i = 0; i < N; i++) {
		for (long long j = 0; j < M; j++) {
			cin >> a[i][j];
		}
	}
 
	vector<long long>A;
	
	cout << saiki(a, A) ;
 
}

参考にさせていただいたサイト

AtCoder ABC 100 D - Patisserie ABC (水色, 400 点) - けんちょんの競プロ精進記録

感想

とても難しい。分かる気がしない。
つまり、例えば次のような入力があったとする。

  1    -2      3
 -4     5     -6
  7    -8     -9
-10    11    -12
 13    -14    15

この時、一列目(1,14,7,-10,13)を＋と決め打ちする。
　　　　二列目(-2,5,-8.11,14)をーと決め打ちする。
　　　　三列目(3,-6,-9,-12,15)を＋と決め打ちする。

すると、一列目[i]＋二列目[i]＋三列目[i]のそれぞれの合計は、(6,-15,6,-33,42)となる。sortして、(-33,-15,6,6,42)と並び変えて、その中で大きい数M個(今回は3個)を選択=>(6,6,42)
それを合計して、答えが54..となる。

決め打ちする通りは2の3乗で8通り。bit全探索を使って解く。