読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.90 品物の並び替え

問題はこちら
No.90 品物の並び替え - yukicoder

制約的に全探索すればいいだけなのだけど、Cにはnext_permutation的なものはないし
自分で実装するのは面倒なので、先に解いていたNo.357をコピペした
いわゆるbitDPと呼ばれている奴
「既に使った商品」をbitで保存して値の小さい方から配るDPをしていく
この配列には「既に使った商品」を先頭から適当に並べた時に得られる最適な点が保存されていく
なぜなら状態の遷移先は常にbitの値が大きくなるからである
(例えばdp[i]がもらうのはiよりも値が小さいところからのみなのでdp[i]から配るときには、ここは最適の値になっている)

イメージしにくいので具体的に。
例えばN=6とし、「既に使った商品の集合」を{2,3,5}とする
(商品のindexは1-basedとする)
==配る側のイメージ==
3番目の商品までは2,3,5で決まっているので「4番目の商品として何を置くか」を考える
1を選ぶとすると、これによりΣ[k=2,3,5]score[k][1]の点が確定する
よってdp[{1,2,3,5}]の値を(必要なら) dp[{2,3,5}]+Σ[k=2,3,5]score[k][1] で更新する
同様にdp[{2,3,4,5}],dp[{2,3,5,6}]にも値を配る
==もらう側のイメージ==
dp[{1,2,3,5}]はdp[{2,3,5}],dp[{1,3,5}],dp[{1,2,3}]から値をもらう
dp[{2,3,5}]から値をもらうときは
<2,3,5の並び>,1
という並びになるが、{1,2,3,5}を使い、かつ、1を4番目に使った時のscoreは、前3つを適当に並べている時に最大になる
なのでこのときもらう値は「4番目を1にするとき」の条件付きで最大
同様に他からもらう時も「4番目をhogeにするとき」の条件付きで最大なので
それら全てにわたってmaxを取れば全体で最大となるものが得られる

実装

int main(){
	int d[512]={},s[9][9]={},i,j,u,v,x,n;
	scanf("%d%d",&n,&x);
	while(x--){
		scanf("%d%d%d",&i,&j,&u);
		s[i][j]=u;
	}
	for(x=0;x<1<<n;x++){
	//xが使用済みの商品の状態を表すbit
	//下からibit目(0-based)が立っていれば、商品iは使用済み
		for(i=0;i<n;i++){
		//次に置く商品として商品iを選ぶ
			if(x&1<<i)continue;
			//使用済みなら選び直し
			u=d[x];
			for(j=0;j<n;j++)if(x&1<<j)u+=s[j][i];
			//そうでないなら、使用済みの商品に起因する点を加算して
			if(d[v=x|1<<i]<u)d[v]=u;
			//配る
		}
	}
	printf("%d",d[(1<<n)-1]);
	//すべての商品を使った時の値
	return 0;
}

まずはわかりやすいところ

d[512],s[9][9],i,j,u,v,x;
main(n){
	for(n=atoi(gets(&n));~scanf("%d%d%d",&i,&j,&u);s[i][j]=u);
	for(;x<1<<n;x++)for(i=0;i<n;d[v=x|1<<i]<u?d[v]=u:0,i++)for(u=d[x],j=0;~x&1<<i&&j<n;j++)u+=x&1<<j?s[j][i]:0;
	i=!printf("%d",d[x-1]);
}

1個ずつfor文潰すよ
1段階目

for(i=0;i<n;d[v=x|1<<i]<u?d[v]=u:0,i++)for(u=d[x],j=0;~x&1<<i&&j<n;j++)u+=x&1<<j?s[j][i]:0;
for(i=n;i--;d[v=x|1<<i]<u?d[v]=u:0)for(u=d[x],j=n;~x&1<<i&&j--;u+=x&1<<j?s[j][i]:0);
for(i=n;i--;d[v=x|1<<i]<u?d[v]=u:0)for(u=d[x],j=n;~x&!!j--<<i;u+=x&1<<j?s[j][i]:0);
//↓形式的に書き換え
for(i=n;~x&!!j--<<i?u+=x&1<<j?s[j][i]:0:(d[v=x|1<<i]<u?d[v]=u:0,u=d[x],j=n,i--););
//このままだと途中で0になって困る可能性がある
//元のfor文において、d[v]の値の更新をjのループ内に持ってきても大丈夫、つまり
for(i=0;i<n;d[v=x|1<<i]<u?d[v]=u:0,i++)for(u=d[x],j=0;~x&1<<i&&j<n;j++)u+=x&1<<j?s[j][i]:0
for(i=0;i<n;i++)for(u=d[x],j=0;~x&1<<i&&j<n;d[v=x|1<<i]<u?d[v]=u:0,j++)u+=x&1<<j?s[j][i]:0
//としてよいので
for(i=n;~x&!!j--<<i?u+=x&1<<j?s[j][i]:0,d[v=x|1<<i]<u?d[v]=u:1:(u=d[x],j=n,i--););
//これで解決
//ただしiがnのときも実行され、n=9のときこのときs[j][i]がやばそうなのでs[i][j]に変えておく
//(これは商品を後ろから並べていったと考えられる)
//さらにdも倍のサイズが必要になり1B増える
//i=n-1とすると2B増えるのでしょうがない

2段階目、3段階目

for(;x<1<<n;x++)for(i=n;~x&!!j--<<i?u+=x&1<<j?s[i][j]:0,d[v=x|1<<i]<u?d[v]=u:1:(u=d[x],j=n,i--););
for(x=-1;~x&!!j--<<i?u+=x&1<<j?s[i][j]:0,d[v=x|1<<i]<u?d[v]=u:1:!(u=d[x],j=n,i--)?i=n,++x<1<<n:1;);
//1B増えたが、for文が1つになったことが重要

for(n=atoi(gets(&n));~scanf("%d%d%d",&i,&j,&u);s[i][j]=u);for(x=-1;~x&!!j--<<i?u+=x&1<<j?s[i][j]:0,d[v=x|1<<i]<u?d[v]=u:1:!(u=d[x],j=n,i--)?i=n,++x<1<<n:1;);
for(n=atoi(gets(&n));~scanf("%d%d%d",&i,&j,&u)?s[i][j]=u:~x&!!j--<<i?u+=x&1<<j?s[i][j]:0,d[v=x|1<<i]<u?d[v]=u:1:!(u=d[x],j=n,i--)?i=n,++x<1<<n:1;);

ここまでのまとめ

d[1100],s[9][9],i,j,u,v,x=-1;
main(n){
	for(n=atoi(gets(&n));~scanf("%d%d%d",&i,&j,&u)?s[i][j]=u:~x&!!j--<<i?u+=x&1<<j?s[i][j]:0,d[v=x|1<<i]<u?d[v]=u:1:!(u=d[x],j=n,i--)?i=n,++x<1<<n:1;);
	i=!printf("%d",d[x-1]);
}

dのindexを逆にしよう
つまり「既に使った商品」ではなく「まだ使ってない商品」をbitで保存
そうすれば出力がちょっと簡単に
さらに最初に問題になっていたiが9のときの処理が解決

d[513],s[9][9],i,j,u,v,x;
main(n){
	for(n=atoi(gets(&n)),x=1<<n;~scanf("%d%d%d",&i,&j,&u)?s[i][j]=u:x&!!j--<<i?u+=x&1<<j?0:s[i][j],d[v=x^1<<i]<u?d[v]=u:1:!(u=d[x],j=n,i--)?i=n,x--:1;);
	i=!printf("%d",*d);
}

nいらなくない?

d[513],s[9][9],i,j,u,x=512;
main(v){
	for(gets(&v);~scanf("%d%d%d",&i,&j,&u)?s[i][j]=u:x&!!j--<<i?u+=x&1<<j?s[j][i]:0,d[v=x^1<<i]<u?d[v]=u:1:!(u=d[x],j=9,i--)?i=9,x--:1;);
	i=!printf("%d",*d);
}

188B