pyてよn日記

一寸先は闇が人生

ABC014: B - 価格の合計

 B 埋め最後の問題.標準ライブラ<bitset><sstream>を初めて使った.これについてはいずれ基礎的なことをまとめたい.

問題


f:id:pytwbf201830:20190104234413p:plain

 問題自体は優しいが 2 進数を理解して解けたらなと思って放置していた.問題の最後の方にも,

今回の問題には直接関係は無いが,部分集合を上記のように表現することで,大きさ n の集合の全ての部分集合(空集合を含む)を 0 ~ (2n - 1)の連続した整数で表現できるので,全列挙を行う際には応用するとよい.

とあるので,それに関しては問題を解いた後にちゃんと調べておきたい.

考察


 問題は簡単.与えられて数字を 2 進数に変換して文字列に直し,それを商品の数だけ左側に 0 埋め(パディング)して, 1 のときに合計金額に足せば良い.2 進数の桁は下から数えるのでそこだけ注意.

解法


www.slideshare.net

 コードは以下.

ABC014: B - 価格の合計

補足:受け取った数字を 2 進数文字列に変換する方法


 提出したコードにも書いてあるが,#include<bitset>#include<sstream>を使う.

decimal to binary string.

参考


2 進数に関する資料.

marycore.jp

marycore.jp

code-mynote.blogspot.com