はまやんはまやんはまやん

hamayanhamayan's blog

Shopping Street [AtCoder Beginner Contest 080 C]

https://beta.atcoder.jp/contests/abc080/tasks/abc080_c

N個の店があり、時間帯1~10について営業しているか与えられる。
F[i][j] := i番目の店で時間帯jに営業しているか(=0:してない, =1:してる)
 
この場合に自分の店を時間帯1~10で営業させるかどうかを考える。
P[i][c] := i番目の店と自分の店の営業帯がc個被っているときに得られる利益
i番目の店と自分の店を比べた時の利益の総和を最大化するように、時間帯1~10で営業させるかどうか決めて、最大値を答えよ。
なお、自分の店は少なくとも1つの営業帯は営業していないといけない。

解法

https://beta.atcoder.jp/contests/abc080/submissions/1830035

自分の店で各営業帯を営業する・しないを決める組合せは最大2^10で大して大きくない。
これを全探索しよう。
するしないの組合せなので、ビットマスクのループを使ってやればいい。
あとは、全ての店に対してそのとき得られる利益を計算して、総和の最大値を答える。

注意が、初期値を-10^9くらいにしておくことと、1つは営業していないといけないので、msk=0は使わない。

#define INF INT_MAX/2
int N, F[101][11], P[101][11];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) rep(j, 0, 10) cin >> F[i][j];
    rep(i, 0, N) rep(j, 0, 11) cin >> P[i][j];
 
    int ans = -INF;
    rep(msk, 1, 1 << 10) {
        int sm = 0;
        rep(i, 0, N) {
            int c = 0;
            rep(j, 0, 10) if (msk & (1 << j)) if (F[i][j]) c++;
            sm += P[i][c];
        }
        ans = max(ans, sm);
    }
    cout << ans << endl;
}