AtCoder Beginner Contest 080 C - Shopping Street (Python)

本日は前まで解けなかった緑diffが今考えたら解けたので紹介したいと思います！

問題はこちら〜

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

とにかく問題文が長い...
見るだけで嫌になってしまいますよね。

1. 問題の概要
2. 問題を見て考えたこと
3. 問題の制約
4. 解説
5. ACコード
6. 最後に

1. 問題の概要

月曜日〜金曜日までの５日間、それぞれ午前・午後に分けた10区間に対して、お店がそれぞれ開店、もしくは閉店している。

joisinoお姉ちゃんは各店が営業している時間帯に店を開くと、その個数に応じた利益が得られます。（説明がとにかく複雑なので詳しくは問題文を見てください...）

このとき、利益の最大値はいくらになるか。

2. 問題を見て考えたこと

冒頭にも書いたようにとにかく問題文が長い...
読解するだけで自分は15分ほどかかってしまいました...

どのように考えれば良いか考えましたが、10区間しかなく、それぞれ営業するかしないかの２択！
これは〇〇しかなさそうですよね？？？

3. 問題の制約

$\displaystyle 1 \leqq N \leqq 100$
$\displaystyle 0 \leqq F_{i,j,k} \leqq 1$
$\displaystyle 1 \leqq i \leqq N$ を満たす全ての整数 i に対して、 $\displaystyle F_{i,j,k} = 1$ を満たす (j, k) が必ず１つ以上存在する
$\displaystyle -10^7 \leqq P_{i,j} \leqq 10^7$
入力は全て整数

4. 解説

こちらは bit全探索のアルゴリズムを用いることでACすることができます！

N 個のお店それぞれ10区間に対して営業するかしないかを考えると、計算量も余裕で間に合います。

bit全探索でjoisinoお姉ちゃんのお店を開くか・開かないかを列挙し、josinoお姉ちゃんが店を開いているかつお店 i が開いていれば個数をカウントし、その個数に対応した利益を格納する配列（今回の場合はplus）の合計値の最大化をすれば解くことができます。

コーナーケースとして、全てのお店が開いていない場合は例外と問題文に書かれているのでその時だけは除外しましょう。（そうしないと入力例２で０が出力されます。）

5. ACコード

from itertools import product

n = int(input())
f = [list(map(int,input().split())) for _ in range(n)]
p = [list(map(int,input().split())) for _ in range(n)]

ans = -10 ** 18 # マイナスの場合もあるので初期値は負のINF
for i in product([0, 1], repeat=10):

    if i.count(0) == 10: continue # 店が１つも空いていない時はNG

    is_open = [0] * n # 各お店とjoisinoお姉ちゃんが両方とも営業している時間帯の数
    for j in range(n):
        for k in range(10):
            if i[k] == 1 and f[j][k] == 1: # どちらも営業している
                is_open[j] += 1

    plus = []
    for j in range(n):
        plus.append(p[j][is_open[j]])

    ans = max(ans, sum(plus))

print(ans)

6. 最後に

つい３ヶ月ほど前にロックアウトで1度出たのですが、全くわからず撤退してしまいました...
でもこうして時間を空けると思いのほか解けてしまいます。

成長を実感できて良かったです！

最後まで見ていただきありがとうございました！