ABC167「C - Skill Up」を個別に反省する

昨日書きましたが、解くのにすごい時間がかかったC問題を見直していきます。

問題と条件

以下を参照

C - Skill Up

これは組み合わせの問題！！と思い「itertools」使って回答しました、こういう時にDFSで解けるようになりたいのでDFS版の回答を作成するかもしれないです。で、一昨日作成した回答は以下

import itertools
N, M, X = map(int, input().split())
book_lists = [list(map(int, input().split())) for i in range(N)]
no_skill_flg = True

for i in range(1, N+1):
   for j in itertools.combinations(book_lists,i):
       sum_list = [0 for _ in range(M+1)]
       for book_date in j:
           for k, l in enumerate(book_date):
               sum_list[k] += l
       if all([s >= X for s in sum_list[1:]]):
           no_skill_flg = False
           if 'ans' in globals():
               ans = min(ans, sum_list[0])
           else:
               ans = sum_list[0]

print(ans if not no_skill_flg else -1)

・「ans」の取りうる最大値は問題の制約条件を見ると「10^5*12」だとわかるので、わざわざ分岐しなくても初期値をそれ以上の数にしておけば良い

・条件が満たされた場合のみ「no_skill_flg」が「False」になるよう記載しているが、条件が満たされた場合のみ「ans」が定義されるので、そもそもフラグは必要なく、以下のように書けばよかったのでは？

print(ans if ’ans’ in globals() else -1)

・本の価格と、本で得られるスキルポイントを一つのリストで運用しているが、分けておいた方が色々便利（属性が違うものを面倒だからと言って全部一緒にリストに入れるのはよくない。多分）

と言った反省と解説動画を見て作った回答が以下です。

N, M, X = map(int, input().split())
book_lists = [list(map(int, input().split())) for _ in range(N)]
max_cost = 10**5*12+1
min_cost = max_cost

for i in range(1, 2**N):
   score_list = [0 for _ in range(M)]
   cost = 0
   for j in range(N):
       if i >> j & 1:
           cost += book_lists[j][0]
           for k in range(M):
               score_list[k] += book_lists[j][k+1]
   if min(score_list) >= X:
       min_cost = min(cost, min_cost)

print(min_cost if not min_cost == max_cost else -1)

この回答の肝は、本は「買う」か「買わない」かの2つのステータスしかないので、それを「0」と「1」のビットで表してるところです。１ビットずつ値を見るのは「n >> i & 1」(n:元の数字、i:確認するビットの位置)を使っています。各ビットをステータスと見做すってのは面白いな。（多分よく使われる手法なんだろうけど。）