betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ Codeforces プログラミング 競技プログラミング お題箱より。 Problem - E - Codeforces 少し前にバチャで扱われて話題になっていましたね。公式解説のDPの正当性が分からないというリクエストだったのですが、私もわからないので（ごめんなさい…）もう少し汎用的に使える解法を書きます。 問題概要 個の要素について重み 、価値 が与えられる。これらの要素から合計重み 以下になるように選んで合計価値を最大化せよ。 制約 解法 ナップサック問題です。 は通らない制約なので、 という制約を活かすことになります。 重みの種類数とその値が非常に小さいときには、重みの最小公倍数に注目した解法が有効な場合があります。重み の最小公倍数は です… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2020%2F01%2F16%2F212705" title=" Educational Codeforces Round 21 E. Selling Souvenirs - ARMERIA" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20n Hatena Blog https://hatena.blog 2020-01-16 21:27:05 rich https://betrue12.hateblo.jp/entry/2020/01/16/212705 1.0 100%