ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

Educational Codeforces Round 21 E. Selling Souvenirs

Codeforces プログラミング競技プログラミング

お題箱より。

Problem - E - Codeforces

少し前にバチャで扱われて話題になっていましたね。公式解説のDPの正当性が分からないというリクエストだったのですが、私もわからないので（ごめんなさい…）もう少し汎用的に使える解法を書きます。

問題概要

$n$ 個の要素について重み $w_{i}$ 、価値 $c_{i}$ が与えられる。これらの要素から合計重み $m$ 以下になるように選んで合計価値を最大化せよ。

制約

$1 \le n \le 100000$
$1 \le m \le 300000$
$1 \le w_{i} \le 3$
$1 \le c_{i} \le 10^{9}$

解法

ナップサック問題です。 $O(nm)$ は通らない制約なので、 $1 \le w_{i} \le 3$ という制約を活かすことになります。

重みの種類数とその値が非常に小さいときには、重みの最小公倍数に注目した解法が有効な場合があります。重み $1, 2, 3$ の最小公倍数は $6$ です。

ここで $k=1, 2, 3$ について、重み $k$ の要素を使う個数を $\frac{6}{k}$ で割った余り $r_{k}$ に注目します。 $(r_{1}, r_{2}, r_{3})$ としてあり得る組み合わせを全探索します。 $(r_{1}, r_{2}, r_{3})$ の値が固定されると、重み $k$ の要素の採用方法は以下のように考えることができます。

重み $k$ の要素を価値の大きいものから順に並べる。まず最初に $r_{k}$ 個の要素を必ず取る。それから先は、 $\frac{6}{k}$ 個の要素（重み合計 $6$ ）をまとめて取ることを $0$ 回以上繰り返す。

つまり、 $k=1, 2, 3$ について最初に取る分を取ってしまったあとは、どこから取っても重み合計 $6$ の単位で取ることになります。つまり各重みの要素から作った重り合計 $6$ の塊を全て混ぜてソートし、容量制限が許す限り価値の大きい塊から貪欲に取っていけば良いです。

最初に取る分の要素がそもそもなかったり、それだけで容量制限を超えてしまう場合は、そのような $(r_{1}, r_{2}, r_{3})$ には解がないということで無視します。

$r_{1}, r_{2}, r_{3}$ が取りうる値の通り数はそれぞれ $6, 3, 2$ 通りであり、全組み合わせを考慮しても十分小さいです。 $(r_{1}, r_{2}, r_{3})$ を全探索することで全てのパターンを網羅できるので、試した中で最も価値合計の大きいものが答えになります。

ACコード

Submission #68934022 - Codeforces

余談

重みの最小公倍数が十分に小さくないと取れない解法なのでなかなか使える機会は少ないかもしれませんが、知っておくと役立つかもしれません。類題として、以下の問題も同様の考え方で解けます。

Problem - E - Codeforces

また公式解説では1種類だけ別で扱うようにすることで同時に考慮すべき種類数を減らしています。これを2つのグループに分けていると見なすと半分全列挙の考え方に繋がります。このように計算量を落とす工夫をすると、解ける幅が少し広がると思います。