Loading [MathJax]/jax/input/TeX/config.js

AtCoder Beginner Contest 080 C – Shopping Street をPython3で解く

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
AtCoder Beginner Contest 080 C – Shopping Street

10個の時間帯に開店するか閉店するかの状態……というわけで、bit全探索でOK。

# AtCoder Beginner Contest 080 C - Shopping Street
# https://atcoder.jp/contests/abc080/tasks/abc080_c
# tag: bit全探索 典型問題 joisinoお姉ちゃん

def main():
    N = int(input())
    # 各店舗のスケジュールの 0 1 列を二進数とみなして数値に変換しておく
    open = [int(input().replace(' ', ''), 2) for _ in range(N)]
    profit = [list(map(int, input().split())) for _ in range(N)]

    result = -10**10

    # bit全探索。自分の店を開ける時間帯を 1 とする。
    for status in range(1, 1<<10):
        tmp_r = 0

        for shop in range(N):
            # 各店舗のスケジュールとビット演算の & を取れば、
            # 残っているビットが重複している時間帯になる。
            dubbed = open[shop] & status

            # 残っているビットを数える。意外とこの書き方が早い。
            cnt = bin(dubbed).count('1')

            tmp_r += profit[shop][cnt]

        if tmp_r > result:
            result = tmp_r

    print(result)

main()
Share

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です