Edit

【pythonでABC184を解説】F - Programming Contest

問題概要

問題ページ

F - Programming Contest
F - Programming Contest

問題ページへ移動する

問題文

高橋くんはプログラミングコンテストに参加します。 このコンテストのコンテスト時間は \(T\) 分間で、 \(N\) 問の問題が出題されます。
高橋くんは超能力者なので、 \(i\) 番目の問題が \(A_i\) 分で解けることが分かっています。
高橋くんは \(N\) 問の中から \(0\) 問以上を、解くのにかかる時間の総和が \(T\) 分以下になるように選び、それらの問題を解きます。
選んだ問題を解くのにかかる時間の総和の最大値を求めてください。

制約

  • 入力は全て整数
  • \(1 \le N \le 40\)
  • \(1 \le T \le 10^9\)
  • \(1 \le A_i \le 10^9\)

問題の考察

ACコード

import sys
import bisect
import itertools


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, t = list(map(int, input().rstrip('\n').split()))
    a = list(map(int, input().rstrip('\n').split()))
    b = a[:len(a) // 2]
    c = a[len(a) // 2:]
    bc = []
    cc = []
    for v in itertools.product(range(2), repeat=len(b)):
        total = 0
        for i in range(len(b)):
            total += b[i] if v[i] == 1 else 0
        bc.append(total)
    for v in itertools.product(range(2), repeat=len(c)):
        total = 0
        for i in range(len(c)):
            total += c[i] if v[i] == 1 else 0
        cc.append(total)
    bc.sort()
    cc.sort()
    mx = 0
    for v in bc:
        pos = bisect.bisect_right(cc, t - v)
        sm = v + cc[pos - 1]
        sm = sm if sm <= t else 0
        mx = max(mx, sm)
    print(mx)


if __name__ == '__main__':
    solve()

-Edit
-