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演算の方法もありそうだが、一旦保留する。