【Python】Atcoder Beginner Contest 167 C問題 解答・解説

この記事は約2分で読めます。

 

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は無限大で初期化しているので別の値に変化していたら(各パターンにおける各アルゴリズムの理解度合計が規定値を超えた場合、)その値を出力することにしました。

解答

各コード+コメント

コードのみ

 参考

Skill Up [AtCoder Beginner Contest 167 C] – はまやんはまやんはまやん (hamayanhamayan.com)

bit全探索についてはこちらの記事で記載しています。

【Python】Atcoderで使われるビット演算・ビットシフト・bit全探索についてまとめる | Best Practice (find-best-practice.com)

 

コメント