AtCoder Beginner Contest Edit

【pythonでABC167を解説】C - Skill Up

問題概要

問題ページ

問題文

競技プログラミングを始めた高橋くんは、学びたいアルゴリズムが \(M\) 個あります。
最初、各アルゴリズムの理解度は \(0\) です。

高橋くんが書店に行くと、\(N\) 冊の参考書が売っていました。\(i\) 番目の参考書 (\(1\leq i\leq N\)) は \(C_i\) 円で売られていて、購入して読むことで、各 \(j\) (\(1\leq j\leq M\)) について \(j\) 番目のアルゴリズムの理解度が \(A_{i,j}\) 上がります。
また、それ以外の方法で理解度を上げることはできません。

高橋くんの目標は \(M\) 個すべてのアルゴリズムの理解度を \(X\) 以上にすることです。高橋くんが目標を達成することが可能か判定し、可能な場合は目標を達成するのに必要な金額の最小値を計算してください。

制約

  • 入力はすべて整数
  • \(1\leq N, M\leq 12\)
  • \(1\leq X\leq 10^5\)
  • \(1\leq C_i \leq 10^5\)
  • \(0\leq A_{i, j} \leq 10^5\)

問題の考察

ACコード

import sys
import itertools


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m, x = list(map(int, input().rstrip('\n').split()))
    ls = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    m_cost = 10 ** 20
    for it_v in itertools.product([True, False], repeat=n):
        cost = 0
        score = [0] * m
        for i in range(n):
            if it_v[i]:
                cost += ls[i][0]
                for j in range(1, m + 1):
                    score[j - 1] += ls[i][j]
        is_ok = True
        for i in range(m):
            if score[i] < x:
                is_ok = False
                break
        if is_ok:
            m_cost = min(m_cost, cost)
    print(m_cost if m_cost != 10 ** 20 else -1)


if __name__ == '__main__':
    solve()

プログラミング

-AtCoder Beginner Contest, Edit
-