C - All Green
C - All Greenについてのメモ。
中途半端に解く配点は 1 種類以下であり、それ以外の配点は完全に解くかまったく解かない。 中途半端に解く配点があるなら、それは完全に解く配点以外の配点の中で最も高い配点である。
と定義すると、再帰関数でできる。
pythonのsetによる集合の扱いは便利だな。
ans = float("inf")
def solve():
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]
# まだ解いてない配点を nokori として持つ
def dfs(i, sum, count, nokori):
global ans
if i == d:
# G 点に満たなければ nokori のうち一番大きいものを解く
if sum < g:
use = max(nokori)
# 解く問題が問題数を超えないように注意
n = min(pc[use - 1][0], -(-(g - sum) // (use * 100)))
count += n
sum += n * use * 100
if sum >= g:
ans = min(ans, count)
else:
# 総合スコア、解いた問題数、まだ解いてない問題を更新
dfs(i + 1, sum, count, nokori)
dfs(i + 1, sum + pc[i][0] * (i + 1) * 100 +
pc[i][1], count + pc[i][0], nokori - {i + 1})
dfs(0, 0, 0, set(range(1, d + 1)))
print(ans)
if __name__ == "__main__":
solve()
bit演算の方法もありそうだが、一旦保留する。