C – Skill Up
方針
n:本の数が1冊から12冊と小さいのでbit全探索が使える問題です。
参考記事よりnが22までならbit全探索で解ける可能性があるようです。
入力
今回の入力はあまり見ないパターンだと思いました。
まずはリストとして金額と本の各アルゴリズムの理解度をまとめて受け取り、
先頭の要素(金額)をリストから抜き出して、別のリストに保存する形にしています。
bit全探索
bit全探索によって全てのパターンを列挙しています。
それぞれのパターンで、合計金額の変数と各アルゴリズムの理解度合計を保存するリストを初期化し、選択した本の金額と各アルゴリズムの理解度を加えていく流れにしました。
numpyの配列を使っているのは、配列内の各要素の四則演算をまとめて計算してくれるからです。
※list1=[1,2,3] list2=[1,2,3]で、各要素ごとに足し算をしたいときは、list1+list2 = [2,4,6]となります。for文などで要素ごとに足し算しなくてよいので楽かと思います。
出力
moneyは無限大で初期化しているので別の値に変化していたら(各パターンにおける各アルゴリズムの理解度合計が規定値を超えた場合、)その値を出力することにしました。
解答
各コード+コメント
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
import numpy as np #入力 n,m,x = map(int, input().split()) #理解度リスト comprehention = [] #各本の金額リスト c = [] for i in range(n): #まずはリストで受け取る tmp = list(map(int, input().split())) #先頭の要素は金額なので、リストから取り出して金額用リストに記録 c.append(tmp.pop(0)) comprehention.append(tmp) #金額の最小値を求めるので無限大で初期化 money = float("inf") #bit全探索 for i in range(2**n): #各パターンでの各アルゴリズムの理解度の合計を記録するnp配列。リストごと四則演算すると要素ごとに計算してくれる。 np_tmp_list = np.zeros(m) #各パターンでの金額合計を記録する変数 tmp_money = 0 #n冊の本から各パターンを列挙 for j in range(n): if (i>>j)&1: #選択した本jの各アルゴリズムの理解度をnp配列に格納 np_comprehention=np.array(comprehention[j]) #選択した本jの各アルゴリズムの理解度を、このパターンでの各アルゴリズムの理解度の合計を記録するnp配列に加え np_tmp_list += np_comprehention #選択した本jの金額を、このパターンでの合計金額に加える tmp_money += c[j] #このパターンでの各アルゴリズムの理解度がxを超えていた場合 if np.all(np_tmp_list>=x): #現在の購入金額と比較して最小値を新たな購入金額とする money=min(money,tmp_money) # 各アルゴリズムの理解度がxを超えた場合(初期化した無限大とはmoneyの値が異なっている場合) if money!=float("inf"): print(money) #全てのパターンで各アルゴリズムの理解度がxを超えなかった場合 else: print(-1) |
コードのみ
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
import numpy as np n,m,x = map(int, input().split()) comprehention = [] c = [] for i in range(n): tmp = list(map(int, input().split())) c.append(tmp.pop(0)) comprehention.append(tmp) money = float("inf") for i in range(2**n): np_tmp_list = np.zeros(m) tmp_money = 0 for j in range(n): if (i>>j)&1: np_comprehention=np.array(comprehention[j]) np_tmp_list += np_comprehention tmp_money += c[j] if np.all(np_tmp_list>=x): money=min(money,tmp_money) if money!=float("inf"): print(money) else: print(-1) |
参考
Skill Up [AtCoder Beginner Contest 167 C] – はまやんはまやんはまやん (hamayanhamayan.com)
bit全探索についてはこちらの記事で記載しています。
【Python】Atcoderで使われるビット演算・ビットシフト・bit全探索についてまとめる | Best Practice (find-best-practice.com)
コメント