【AtCoder版！蟻本】ABC104 C - All Green【bit全探索】 - ebisukeプログラミング初心者脱出黙示録

f:id:ebisuke33:20210317155548p:plain
AtCoder版！蟻本のbit全探索で類題としてあげられているABC104 CをPythonで解いていきます。

リンク

AtCoder Beginner Contest 104 C - All Green

問題文

プログラミングコンペティションサイト AtCode は、アルゴリズムの問題集を提供しています。それぞれの問題には、難易度に応じて点数が付けられています。現在、
1 以上 D 以下のそれぞれの整数 i に対して、100i 点を付けられた問題が pi 問存在します。これらの p1+…+pD 問が AtCode に収録された問題のすべてです。
AtCode のユーザーは総合スコアと呼ばれる値を持ちます。ユーザーの総合スコアは、以下の 2 つの要素の和です。
基本スコア: ユーザーが解いた問題すべての配点の合計です。
コンプリートボーナス: 100i 点を付けられた pi 問の問題すべてを解いたユーザーは、基本スコアと別にコンプリートボーナス ci 点を獲得します (1≤i≤D)。
AtCode の新たなユーザーとなった高橋くんは、まだ問題を 1 問も解いていません。彼の目標は、総合スコアを G 点以上にすることです。このためには、少なくとも何問の問題を解く必要があるでしょうか？

制約

・1≤D≤10
・1≤pi≤100
・100≤ci≤10^6
・100≤G
・入力中のすべての値は整数である。
・ci,G はすべて 100 の倍数である。
・総合スコアを G 点以上にすることは可能である。

解答例

# bit全探索、貪欲法
D, G = map(int,input().split())

P = []
C = []
for i in range(D):
    p, c = map(int,input().split())
    P.append(p)
    C.append(c)

#最小の回答数
ans = 1e9
for bit in range(2**D): # bit 1で問題コンプリート
    total = 0 # 合計得点
    num = 0 # 回答数
    for i in range(D):
        if (bit >> i) & 1:
            total += 100 * (i+1) * P[i] + C[i]
            num += P[i]
    if total >= G: # 問題コンプリートだけでGを超える場合
        ans = min(ans,num)
    else:
        for j in reversed(range(D)): # 得点が大きいほうから貪欲法
            if (bit >> j) & 1: # コンプリートは飛ばす
                continue
            target = G - total
            if target <= P[j] * (100 * (j+1)): # 問題を解くとtotalがGを超える場合
                num += -(-target // (100 * (j+1))) # 切り上げ！
                ans = min(ans,num)
                break
            else:
                total += 100 * (j+1) * P[j]
                num += P[j]

print(ans)

解説

総合スコアを G 点以上にするために最小の問題数を答える問題です。
総合スコアは1問解くごとにもらえる基本スコア（例：A問題なら100点、B問題なら200点）と、コンプリートボーナス（例：A問題すべて解くとc1点）の合計です。

問題をすべて解く難易度の組み合わせをbit全探索し、G点を超えなかったら配点が高い問題から貪欲に解いていく方針です。

合計得点をtotal、問題の回答数をnumとおき、bitが1ならその難易度の問題をすべて解いたことにしました。
得点はその難易度の配点×問題数とコンプリートボーナスを足し合わせた値です。
もし、コンプリートだけでG点以上になった場合は、解答となるansと比較して小さければ代入します。

コンプリートだけでG点に満たなかった場合は、bit情報を用いてコンプリートしていない問題を配点の高い順に解いていくシミュレーションをしました。
この貪欲法でコンプリートしてもボーナスを考慮していません。
その場面はbit全探索でカバーされるはずなので最終的な解答には影響がないと思います。

この探索を終えてans変数を出力すればACでした。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク