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

メモ

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

yukicoder No.286 Modulo Discount Store

問題はこちら
No.286 Modulo Discount Store - yukicoder

yukicoder No.90 品物の並び替え - メモ
これと同様にしてbitDP
ほとんど同じなので通常解説は省略

int main(){
	int d[99999]={},a[20],i,j,k,n,m;
	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%d",a+n);
	for(i=0;i<1<<n;i++){
		//既に買った商品のbitが立っている
		for(j=0;j<n;j++){
			//j番目の商品を新たに買う(jは0-based)
			if(i>>j&1)continue;
			for(m=k=0;k<n;k++)m=(m+(i>>k&1)*a[k])%1000;
			//既に買った商品の合計金額を求めて
			m=a[j]<m?0:a[j]-m;
			//a[j]番目の商品の割引後の価格を求め
			!d[i^1<<j]|d[i^1<<j]>d[i]+m?d[i^1<<j]=d[i]+m:0;
			//更新できるかチェック
		}
	}
	i=!printf("%d",d[(1<<n)-1]);
}

まずはいつもの

d[99999],a[20],i=65536,j,k,n;
main(m){
	for(gets(a);~scanf("%d",a+j++););
	for(;i--;)
		for(j=16;j--;m=a[j]<m?0:a[j]-m,!d[k=i^1<<j]|d[k]>d[i]+m?d[k]=d[i]+m:0)
			for(m=0,k=16;k--;m%=1000)m+=(~i>>k&1)*a[k];
			//既に買った商品を再度買ったら高くつくのは当たり前なのでチェックを省略
	i=!printf("%d",*d);
}

213B

for圧縮

for(;i--;)for(j=16;j--;m=a[j]<m?0:a[j]-m,!d[k=i^1<<j]|d[k]>d[i]+m?d[k]=d[i]+m:0)for(m=0,k=16;k--;m%=1000)m+=(~i>>k&1)*a[k];
for(;i--;)for(j=15;k--?m=(m+(~i>>k&1)*a[k])%1000,1:(m=a[j]<m?0:a[j]-m,!d[k=i^1<<j]|d[k]>d[i]+m?d[k]=d[i]+m:0,m=0,k=16,j--););
for(;k--?m=(m+(~i>>k&1)*a[k])%1000,1:(m=a[j]<m?0:a[j]-m,!d[k=i^1<<j]|d[k]>d[i]+m?d[k]=d[i]+m:0,m=0,k=16,j--)?:(j=15,i--););
//最初にmが0になっている必要がある

んんん?縮まない?

細かなバリエーションも考えたけれどどれも同じ長さにしかならなかった

for(;k--?m=(m+(~i>>k&1)*a[k])%1000,1:(m=a[j]<m?0:a[j]-m,!d[k=i^1<<j]|d[k]>d[i]+m?d[k]=d[i]+m:0,m=0,k=16,j--)?:(j=15,i--););
for(;k--?m=(m+(~i>>k&1)*a[k])%1000,1:(m=a[j]<m?0:a[j]-m,!d[k=i^1<<j]|d[k]>d[i]+m?d[k]=d[i]+m:0,m=0,k=16,!j--?j=15,i--:1););
for(;k--?m=(m-(~i>>k&1)*a[k])%1000,1:(m+=a[j],m<0?m=0:0,!d[k=i^1<<j]|d[k]>d[i]+m?d[k]=d[i]+m:0,m=0,k=16,!j--?j=15,i--:1););

scanfのfor文と合体させると、scanfが多いせいでTLEになる

悲しいので圧縮する前ので提出した