【ABC167 C】「Skill Up」を解く【Python3】

コンテスト一覧へ

 

競プロのためにアルゴリズムを学び始めた高橋君が、目標を達成するのに必要な最低金額を計算する問題です。

提出
n, m, x = map(int, input().split())
ca = [list(map(int,input().split())) for _ in range(n)]

add = []

for i in range(2**n):
    skill = [0]*(m+1)
    for j in range(n):
        if ((i>>j) & 1):
            skill = list(map(sum, zip(skill, ca[j])))
    if min(skill[1:])>=x:
        add.append(skill)

if add:
    add.sort()
    print(add[0][0])
else:
    print(-1)

それぞれの参考書を「買った場合」「買わない場合」の全パターンは、参考書が最大で12冊であるので、最大「212=4096」になります。

ということで、全パターンを調べ、「M個のすべてのアルゴリズムの理解度がX以上」かつ、「金額が最小値のもの」を求めても時間は間に合います。

 

二択のものの全パターンを調べる方法として「bit全探索」があります。

「>>」はビットシフト演算子といい、2進数を指定の数だけ右にシフトします

「<<」は同様に左にシフトします。

x = 13
print(bin(x))                       # > 0b1101
print(x << 1)                       # > 26
print(bin(x << 1))                  # > 0b11010
print(x >> 1)                       # > 6
print(bin(x >> 1))                  # > 0b110

「0b」は2進数の先頭につく文字列です。

 

「&」は論理積といい、2つの数字の両方が1の場合のみ、1を返します。

x = 7
y = 19
print(bin(x),bin(y))                # > 0b111 0b10011
print(x & y)                        # > 8
print(bin(x & y))                   # > 0b1000

 

問題に戻ると、

if ((i>>j) & 1):

という箇所は、i を j 回右にシフトさせ、1との論理積を計算しています。

i を j 回右にシフトしたときに、右端にある数値が(2進数で)1であるかどうか、ということです。

「買った場合」を1、「買っていない場合」を0と考えているため、1のときには参考書のスキルをリスト「skill」に足しています。

 

参考書の合計スキルのいずれかが、x以下であっては意味がないので、

if min(skill[1:])>=x:
    add.append(skill)

を使って、スキルの最小値がx以上かどうかを判定しています。

x以上であれば、リスト「add」に加えます。

(skill[0]は参考書の値段なので、それ以外を判定します)

最終的に、「add」をソートして、先頭にあるものが答えなので、その値段を出力します。

addが空リストだった場合、条件に合うものがなかったということなので、「-1」を出力します。

スポンサーリンク

【ABC167】解説記事リスト

コンテスト一覧に戻る

1 COMMENT

かんちゃん

Bit全探索は、なかなか身に付きません。
Bit全探索の中の
skill = list(map(sum, zip(skill, ca[j])))
は、とても思いつかないコードです。
map,sum,zipの使い方がカッコ良いです。
自分も、こういうコードが書けるようになりたいです。
自分には無理かもしれませんが、、、(*^-^*)

返信する

コメントを残す

メールアドレスが公開されることはありません。