ABC080 C

bit全検索を使って解く

問題文

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

入力

営業時間 F と利益 Pの二次元配列を作成

F = [list(map(int, input().split())) for i in range(N)]
P = [list(map(int, input().split())) for i in range(N)]

ロジック

• 制約条件から取りうる利益の最小値は -10**7 * 10 なので、ansの初期値はそれよりも小さい数にする

  ans = -10**10

• 自分の店を営業する・しないをbitで表現し、全ての組み合わせ 2**10通りを全検索する
  但し、「1つ以上の時間帯で営業しなければならない」制約条件があるため 0000000000b は除外して、ループは 0000000001bからスタート

  for b in range(1, 2**10):

• 各営業時間について、自分の店と店iの両方が営業しているかどうかをチェックして、該当する個数をカウントする

  ch = [0] * N
  for i in range(10):
  if (b>>i) & 1:
      for j in range(N):
          ch[j] += F[j][i]

• 商店街にあるN個の店ごとに、自分の店と共通する営業時間の個数が ch に格納されたので、それを元に店の利益を計算する

  ma = 0
  for k in range(N):
  ma += P[k][ch[k]]

• 2**10通りの組み合わせについて、利益の比較をして最大値を求める

  ans = max(ans, ma)

提出したコード

N = int(input())
F = [list(map(int, input().split())) for i in range(N)]
P = [list(map(int, input().split())) for i in range(N)]

ans = -10**10

for b in range(1, 2**10):
    ch = [0] * N
    for i in range(10):
        if (b>>i) & 1:
            for j in range(N):
                ch[j] += F[j][i]
    ma = 0
    for k in range(N):
        ma += P[k][ch[k]]
    ans = max(ans, ma)
print(ans)

https://atcoder.jp/contests/abc080/submissions/24764993