バイトの競プロメモ

主に競技プログラミング

D - バレンタインデー AtCoder Beginner Contest 018

問題概略
N人の女子とM人の男子がいる。女子はいくつかのチョコを持っており、渡したい男子とその時の幸福度がある。
女子P人と男子R人を選んで幸福度を最大にしたい。

制約
1<=all<=18

解法
愚直にやると 18c9 * 18c9 で 48000 * 48000 ぐらいになる。
片方を固定したくなる。
例えば女子の組が決まっていれば、ある男子を入れた時のスコアが分かる
具体的にはチョコレートを見ていって、対応する女子がグループにいれば男子に加算すればいい
男子の結果は独立しているため、貪欲に選べる


public static void main(String[] args) {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        M = ni();
        P = ni();
        Q = ni();
        R = ni();
        long startTime = System.currentTimeMillis();
        int[][] cho = new int[N][M];
        for (int i = 0; i < R; i++) {
            cho[ni() - 1][ni() - 1] = ni();
        }
        for (int bit = 0; bit < (1 << 18); bit++) {
            if (Integer.bitCount(bit) != P) continue;
            int[] ma = new int[M];
            for (int ni = 0; ni < N; ni++) {
                for (int mi = 0; mi < M; mi++) {
                    if (bitGet(bit, ni)) {
                        ma[mi] += cho[ni][mi];
                    }
                }
            }
            revSort(ma);
            long res = 0;
            for (int i = 0; i < Q; i++) {
                res += ma[i];
            }
            chMax(res);
        }
        System.out.println(maxRes);

        long endTime = System.currentTimeMillis();
        System.err.println(endTime - startTime);
    }