JOI2011本戦 第二問「古本屋」

はい、今日もちょびちょび書いていきますよ〜


絶対DPは出るだろうと思ってたら案の定、出たっていう話ですね。
ただ、DPに至るまでにワンステップありましたね。

最初は、naiさんがおまけとして説明してた貪欲法かな〜、と思ったんですが割とすぐダメだと気付いた。
まあ、解説の第一段階として貪欲法での解き方(解けないけど)を。

貪欲法

ジャンルの概念を無視して考えるならば、
ソートをして高い本から順番に k 冊売ればいいですよね?

それを発展させて、
・ジャンルごとにソートをして、そのソート列に細工をして、貪欲法。
っていう方針を立てます。

「細工」とは?

ジャンル1の本が4冊あるとする。
それぞれの本の値段を、c1,c2,c3,c4とする。
1冊売ると c1円
2冊売ると c1+c2+(1×2)円
3冊売ると c1+c2+c3+(2×3)円
4冊売ると c1+c2+c3+c4+(3×4)円
になる。
ここで「同じジャンルの本が1冊増えると何円収入が増えるか」を考える。
1冊のときと2冊のときの差は、c2 + 2円
2冊のときと3冊のときの差は、c3 + 4円
3冊のときと4冊のときの差は、c4 + 6円
何となく法則性が見つけられますね。 つまり、
・i-1冊のときと i 冊のときの差は、ci + 2*(i-1)円
ってなわけです。
よって、「細工」とは
・ソート列の i 番目に、2*(i-1)を足す。
ですね。


というわけで、こういうソースが書けます。

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define drep(i,n) for(int i = n; i >= 0; i--)
#define pb push_back
using namespace std;

int main(){
	int n, k, c, g, ans = 0, x, y;
	scanf("%d%d", &n, &k);
	vector<int> b[11];
	queue<int> q[11];
	
	rep(i,n){
		scanf("%d%d",&c,&g);
		b[g].pb(c);
	}
	
	rrep(i,10) sort(b[i].begin(), b[i].end(), greater<int>()); 
	
	rrep(i,10) rep(j,b[i].size()) q[i].push(b[i][j] + 2*j);
	
	
	rep(i,k){
		x = 0;
		rrep(j,10){
			if (!q[j].empty() && x < q[j].front()) {
				x = q[j].front();
				y = j;
			}
		}
		
		ans += x;
		q[y].pop();
	}
	
	printf("%d\n",ans);
	
	return 0;
}

しかし、このソースだとしょっぱなからバグります。

7 4
14 1
13 2
12 3
14 2
8 2
16 3
11 2

この入力データの正解は60ですが、上のソースだと59になります。
何がおかしいのか、実験してみましょう。


まずはジャンルごとにソートします。

1 : 14
2 : 14 13 11 8
3 : 16 12

次に「細工」をします。

1 : 14
2 : 14 15 15 14
3 : 16 14

すると、ジャンル2が降順ではなくなっています!
これがバグを生み出しているんですね。


というわけで、貪欲法はうまくいきません。
ではどうするか。


とりあえず、データの持ち方を工夫しましょう。
すなわち、本それぞれの値段を記録するのではなく、
各ジャンルから i 冊買う時の最高の収入
を記録するのです。
上のサンプルデータだとこうなります。

1 : 14
2 : 14 29 44 58
3 : 16 30

さて、ここからどうするかというと、
DPです! 動的計画法です! ダイナミックプログラミングです!!


いや、まあつまり
ジャンル i までの本を j 冊売るときの最高の収入 でDPるんです!
DPが分からない人は、表紙に蟻が書いてある本でも読んでもらうとして、
最終的にはこうなります。

#include<cstdio>
#include<algorithm>
#include<vector>
#include<functional>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define drep(i,n) for(int i = n; i >= 0; i--)
#define pb push_back
using namespace std;

int dp[2000];

int main(){
	int n, k, c, g;
	scanf("%d%d", &n, &k);
	vector<int> b[11], v[11];
	
	rep(i,n){
		scanf("%d%d",&c,&g);
		b[g].pb(c);
	}
	
	rrep(i,10){
		sort(b[i].begin(), b[i].end(), greater<int>());
		v[i].pb(0);
	}
	
	rrep(i,10) rep(j,b[i].size()) v[i].pb(v[i][j] + b[i][j] + j*2);
	
	rrep(i,10){
		drep(j,k){
			for(int h = max(0,j-(int)v[i].size()+1); h < j; h++){
				dp[j] = max(dp[j], dp[h] + v[i][j-h]);
			}
		}
	}
	
	printf("%d\n",dp[k]);
	
	return 0;
}

〜変数説明〜
dp[2000] : DPテーブル(再利用する) dp[j]は、j 冊売るときの最高の収入。
n, k, c, g : 入力用
b[11] : bookのb 各ジャンル(1~10)の本の値段を入力し、ソートする。
v[11] : valueのv v[i][j]は、ジャンル i の本を j 冊売るときの最高の収入。


というわけで、たぶんあと3日くらい続きま〜す/