概要
初めてQiitaに記事を投稿します。Shunと申します。
競プロの中級レベルの問題の解説（備忘録？）となります。
今回取り上げるのは、【CodeChef March Cook-Off 2019】Div1の3問目、【Music Shopping】です。
見た目ですぐにナップサック問題と分かる上、非常にシンプルな問題にもかかわらず、意外と難しかった問題。
今後他コンテストで類似問が出る可能性も高そうなのでピックアップしました。
問題
原文
As everybody knows, Reza Shiri is the favourite Iranian artist. Since we love Reza Shiri and his songs, we never download them for free. Reza Shiri’s songs must be purchased from authorised stores. However, what if there is not enough money to buy all the songs?
There are N songs (numbered 1 through N) and M albums (numbered 1 through M) available. For each valid i, the i-th song has greatness vi, price pi and belongs to the album ai. For each valid i, the i-th album has price bi. If we buy an album, then all songs from this album count as bought. It is also possible to buy any songs individually.
Your task is simple ― given the budget P (the amount of money we have), calculate the maximum total greatness of songs we can buy. The total greatness is defined as the sum of greatness values of all distinct songs that are bought (either individually or as part of albums).
意訳
$M$種類のアルバムがあり、各アルバムの曲を合計すると$N$曲ある。
それぞれの曲$i$はアルバム$a_i$に属し、素晴らしさ$v_i$を持ち、値段$p_i$で買うことができる。
また、アルバム単位で曲をまとめて買うこともでき、アルバム$j$に対し値段$b_j$が設定されている。
金額$P$で曲およびアルバムを買ったとき、得られる$v$の総和の最大値を求めよ。
制約
$1≤N,M,P≤1,000$
$1≤b_i,p_i≤P$
$1≤v_i≤10^6$
$1≤a_i≤M$
考え方
明らかに、アルバムに関する記述がなければただのナップサック問題です。
しかしこの問題では、アルバムを買うとそのアルバムに属する曲を単曲買いできなくなるという排他制約のため、ナップサック問題と同じDPでは解けません。
ここで、アルバム1つ1つに対しては普通にDPを回せることに気付けるかどうかがポイントとなります。
具体的には以下の手順により、各アルバムごとのDPを実行します。
- アルバム内の曲だけで通常のナップサックDPを実行。($dp[i][j]$を、i番目の曲まで、金額jを使って達成できる素晴らしさの最大値とする）
- DP実行後、アルバムの価格b以上の要素をすべて$\sum_{k=1}^n v_k$で埋める。
例えば以下のテストケースを考えます。
5 2 24
1 7 2
1 5 2
1 4 1
2 9 1
2 13 2
10 15
この場合にアルバム1に関するDPを回すと以下の結果が得られます（太字がアルバムを購入した場合）。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 2 | 2 | 2 | 2 | 3 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 |
また、アルバム2に関するDPを回すと以下の結果が得られます（太字がアルバムを購入した場合）。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
以上の結果を用いて、アルバム1と2に関して金額$j$を使って得られる素晴らしさ$v$の最大値は、【アルバム1に金額$x$、アルバム2に金額$j-x$使って得られる$v$】を$x$に関して最大化すればよいです。
上記アルバム1と2に対して上記アルゴリズムを実行すると最終的に以下の結果になります。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 2 | 2 | 2 | 2 | 3 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 6 | 6 | 6 | 6 | 7 | 7 |
したがって答えは7ですね。アルバムが3つ以上の場合は順番に行っていけばよいです。
これを全ての$x$に対して実行すると時間計算量で$O(MP^2)$となりTLEとなってしまいますが、【アルバムを足し合わせる際に考慮しなければならない金額$x$の値は、金額$x-1$に対して$v$が異なるものだけ】ということを利用し計算量を抑えることでACとなりました（その場合の時間計算量はわかりませんが、実行時間0.2s程度なので$O(10^7)$には抑えられていそうです）。
ソースコード
Submit時そのままなので汚いです。暇なときにもう少しコード整理します。
（ライブラリ部は省略）
private static FastScanner sc = new FastScanner();
private static boolean DEBUG_FLG = false;
public static void main(String[] args) {
int N = sc.nextInt();
int M = sc.nextInt();
int P = sc.nextInt();
Song[] songs = new Song[N];
int[] albcnt = new int[M];
int[] albvsum = new int[M];
for(int i=0; i<N; i++) {
songs[i] = new Song(sc.nextInt()-1, sc.nextInt(), sc.nextInt());
albcnt[songs[i].a]++;
albvsum[songs[i].a] += songs[i].v;
}
Arrays.sort(songs, (a, b) -> a.a - b.a);
int[] b = new int[M];
for(int i=0; i<M; i++) {
b[i] = sc.nextInt();
}
int[][] dp = new int[M+1][P+1];
int songidx = 0;
for(int i=0; i<M; i++) {
int[][] albdp = new int[albcnt[i]+1][P+1];
for(int j=0; j<albcnt[i]; j++) {
for(int k=1; k<=P; k++) {
if(k >= songs[songidx].p) {
albdp[j+1][k] = Math.max(albdp[j][k], albdp[j][k-songs[songidx].p]+songs[songidx].v);
} else {
albdp[j+1][k] = albdp[j][k];
}
}
songidx++;
}
for(int j=b[i]; j<=P; j++) {
albdp[albcnt[i]][j] = albvsum[i];
}
HashSet<Integer> chgIdx = new HashSet<Integer>();
chgIdx.add(0);
int tmp = albdp[albcnt[i]][0];
for(int j=1; j<=P; j++) {
if(tmp != albdp[albcnt[i]][j]) {
chgIdx.add(j);
tmp = albdp[albcnt[i]][j];
}
}
for(int pidx : chgIdx) {
for(int k=pidx; k<=P; k++) {
if(albdp[albcnt[i]][pidx] + dp[i][k-pidx] >= dp[i+1][k]) {
dp[i+1][k] = albdp[albcnt[i]][pidx] + dp[i][k-pidx];
}
}
}
for(int k=1; k<=P; k++) {
if(dp[i+1][k] < dp[i+1][k-1]) {
dp[i+1][k] = dp[i+1][k-1];
}
}
}
System.out.println(dp[M][P]);
}
static class Song {
int a;
int p;
int v;
public Song(int a, int p, int v) {
this.a = a;
this.p = p;
this.v = v;
}
}
次回はまだ未定。
マラソンマッチに最近はまりつつあるので、それなりの成績残せたら記事書きます。
あとはcodecademyの紹介記事でも書いておこうかな…