ABC104 C - All Green

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import datetime

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

# 再帰の制限設定
sys.setrecursionlimit(10000000)


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


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


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def ceiling(num, div):
    return (num + div - 1) // div


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

    D, G = il()

    PC = []
    for _ in range(D):
        p, c = il()
        PC.append([p, c])

    ret = INF
    for i in range(1 << D):
        ans_cnt, point = 0, 0
        used = [False] * D
        for j in range(D):
            if (i >> j) & 1:
                # 全問正解
                p, c = PC[j]
                point += p * (100 * (j + 1)) + c
                ans_cnt += p
                used[j] = True
        for j in reversed(range(D)):
            if used[j]:
                continue
            if point < G:
                # 点数が足りない場合には
                # 配点の高い問題から回答を行う
                p, _ = PC[j]
                cnt = min(ceiling((G - point), (100 * (j + 1))), p)
                point += cnt * (100 * (j + 1))
                ans_cnt += cnt
        if point >= G:
            ret = min(ret, ans_cnt)
    print(ret)


if __name__ == '__main__':
    main()

考え方

ある問題jを全て回答して、足りない残りの点数を配点の高い順に回答します。
この時のjは複数個存在する場合もありますが、まったく存在しない場合もあります。
つまり、全ての問題に対してコンプリートボーナスが獲得できるように回答する場合や
全ての問題に対してコンプリートボーナスが獲得できないように回答する場合を全探索します。

回答にはbit全探索を用いました。
各問題j ( 1<= j <= D )に対して、コンプリートボーナスが獲得できるように回答できる場合と、
コンプリートボーナスが獲得できないように回答する場合を全探索します。
その後、足りない点数分だけ、配点の高い問題が回答を行い、
目標点数を満たす最小回答数の探索を行ないます。