山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

AtCoder Beginner Contest 100 D - Patisserie ABC

8通りで評価する

abc100.contest.atcoder.jp

どうやって解くのか分からなかったので解説を見ました。

典型的な問題なんでしょうか?

詳しくは解説を読むといいと思います。

コード

import java.util.Arrays;
import java.util.Scanner;

public class ProblemD {
    public static int []S = new int[3];
    static int [][]bit = new int[8][3];
    public static int n = 3;
    public static int cnt = 0;;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        long []x = new long[N];
        long []y = new long[N];
        long []z = new long[N];

        for(int i = 0; i < N; i++) {
            x[i] = scan.nextLong();
            y[i] = scan.nextLong();
            z[i] = scan.nextLong();
        }
        scan.close();
        long []p = new long[N];
        rec(0);

        long max = 0;
        for(int i = 0; i < 8; i++) {
            int sign1, sign2, sign3;
            sign1 = 1;
            sign2 = 1;
            sign3 = 1;
            if(bit[i][0] == 0) {
                sign1 = -1;
            }
            if(bit[i][1] == 0) {
                sign2 = -1;
            }
            if(bit[i][2] == 0) {
                sign3 = -1;
            }
            for(int j = 0; j < N; j++) {
                p[j] = sign1 * x[j] + sign2 * y[j]
                        + sign3 * z[j];
            }
            Arrays.sort(p);
            long temp = 0;
            for(int j = N - 1; j >= N - M; j--) {
                temp += p[j];
            }
            if(max < temp) {
                max = temp;
            }

        }
        System.out.println(max);

    }
    public static void rec(int k) {
        if(k == n) {
            for(int i = 0; i < n; i++) {
                bit[cnt][i] = S[i];
            }
            cnt ++;
            //disp(S);
            return;
        }
        rec(k + 1);
        S[k] = 1;
        rec(k + 1);
        S[k] = 0;
    }
    public static void disp(int []A) {
        for(int i = 0; i < A.length - 1; i++) {
            System.out.print(A[i] + ", ");
        }
        System.out.println(A[A.length -1]);
    }
}