AtCoder Beginner Contest 100 解説備忘録

前書き

AtCoder Beginner Contest 100 を解いてみた．解けなかった問題の備忘録．

D問題

[問題はこちら]

・N個のケーキのうち，M個のケーキを取る．
・そのうち，(綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) が最大になるように選ぶ．すなわち，

$\max \{ |x_1+x_2+\cdots +x_M| + |y_1+y_2+\cdots +y_M| + |z_1+z_2+\cdots +z_M| \}$

を求めたい．

・$_NC_M$通りをループしてしまうのは明らかにタイムアウト．

・ここで絶対値の意味を考える．

$
|X|=
\begin{cases}
X ~~~~(X\geqq 0)\\
-X ~ ~(X<0)
\end{cases}
$

となることから，絶対値をとるときは 「(絶対値の中身) × (+1)」か 「(絶対値の中身) × (-1)」の二通りを考えれば良い．

・今回の場合，$|X|,|Y|,|Z|$ の3つの絶対値の和を考えるのだから，$2^3$通りを考えれば良い．

main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <sstream>
#include <bitset>
#include <stack>
#include <cstdlib>
#include <utility> //pair

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

typedef long long ll;

using namespace std;

ll a[8][3] = {{1,1,1},{1,1,-1},{1,-1,1},{1,-1,-1},{-1,1,1},{-1,1,-1},{-1,-1,1},{-1,-1,-1}};


int main() {

    ll n,m;
    cin >> n >>m;

    vector<ll> x(n),y(n),z(n);

    FOR(i, 0, n){
        cin >> x[i] >> y[i] >> z[i];
    }

    ll ans = -(1ll<<60);
    FOR(i, 0, 8){
        vector<ll> tmp(n);
        FOR(j, 0, n){
            tmp[j] = x[j] * a[i][0] + y[j] * a[i][1] + z[j] * a[i][2] ;
        }
        sort(tmp.begin(),tmp.end(),greater<ll>());
        ll sum=0;
        FOR(j, 0, m){
            sum += tmp[j];
        }
        ans = max(sum,ans);
    }

    cout << ans << endl;


    return 0;
}

あとがき

精進します．