ABC167 C - Skill Up

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import collections
import itertools
import heapq

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M, X = il()
    CA = [il() for _ in range(N)]

    ret = MAX
    for n in range(1 << N):
        k = 0
        A = [0] * M
        for j in range(N):
            c, *alist = CA[j]
            if n >> j & 1:
                k += c
                for i in range(len(alist)):
                    A[i] += alist[i]
            if all([a >= X for a in A]):
                ret = min(ret, k)
                break
        else:
            continue

    print(-1 if ret == MAX else ret)


if __name__ == '__main__':
    main()

考え方

N冊の参考書に対して、購入するか否かの2択を全探索する。
購入する、しないの2択なので探索はbit全探索で行うことができ、
計算量はO(2**N)となる。

実装は過去の自分の記事を参考した。
1をNビット左にシフトした範囲を探索範囲とし、
n >> j & 1で参考書を購入した場合、しない場合を判定する。
理解度が全てXを超えた時点の最小金額を回答とした。