問題概要

すでに $N$ 個の店が出店している商店街で、新たに店を開こうとしている。

どの店についても 10 個の時間帯があり、それぞれについて open・close を選ぶことができる。すでに出店している店 $i$ が、10 個の時間帯のどこで open しているかについては、入力として与えられる（ $N \times 10$ の 0, 1 で与えられる）。

新たに開く店について、10 個の時間帯それぞれで open・close のいずれにするかを決めたい。open・close を決めたときの利益は次のように決まる。

(利益)
すでに出店している各店 $i$ について、店 $i$ と新しく開く店がともに open である時間帯の個数を $C_{i}$ とする。このとき、

$\sum_{i} P_{i, C_{i}}$

とする（ $P_{i, k}$ は入力で与えられる）。

制約

$1 \le N \le 100$

考えたこと

競プロするときは、常に最初に「全探索できないか」を考えよう。今回も、10 個の時間帯それぞれについて、open・close を決める方法が

$2^{10} = 1024$ 通り

がある。この程度なら全探索は容易にできそうである。

今回は、具体的には、ビット全探索がバッチリである。ビット全探索については次の記事を参照。

drken1215.hatenablog.com

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    const int INF = 1<<30;
    int N;
    cin >> N;
    vector F(N, vector(10, 0)), P(N, vector(11, 0));
    for (int i = 0; i < N; i++) for (int j = 0; j < 10; j++) cin >> F[i][j];
    for (int i = 0; i < N; i++) for (int j = 0; j < 11; j++) cin >> P[i][j];

    int res = -INF;
    for (int bit = 1; bit < (1<<10); bit++) {
        int profit = 0;
        for (int i = 0; i < N; i++) {
            int num = 0;
            for (int j = 0; j < 10; j++) {
                if (F[i][j] == 1 && (bit & (1 << j))) num++;
            }
            profit += P[i][num];
        }
        res = max(res, profit);
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 080 C - Shopping Street (2Q, 緑色, 300 点)

問題概要

制約

考えたこと

コード