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

メモ

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

yukicoder No.27 板の準備

問題はこちら
No.27 板の準備 - yukicoder

作りたい板の長さが30以下なので用意する板の長さも30以下
ということは用意する3種類の板の長さの組として考えられるものは30C3=4060通り
各場合について、何枚用意すればいいかDPで調べる

int main(){
	int d[70],a[4],i[3],j,m=120,t;
	//120は自明な上界。長さ1の板が120枚あれば必ず作れる
	for(j=0;j<4;j++)scanf("%d",a+j);
	for(i[0]=1;i[0]<31;i[0]++)for(i[1]=i[0]+1;i[1]<31;i[1]++)for(i[2]=i[1]+1;i[2]<31;i[2]++){
		for(t=1;t<70;t++)d[t]=9999;
		//dの初期化はmの初期値以上で
		d[0]=0;
		for(t=0;t<31;t++){
			for(j=0;j<3;j++)if(d[t+i[j]]>d[t])d[t+i[j]]=d[t]+1;
		}
		//配るDP
		t=0;
		for(j=0;j<4;j++)t+=d[a[j]];
		m=m>t?t:m;
	}
	printf("%d",m);
	return 0;
}

3重ループウザいのでこの部分を
for(i=1;i<27000;i++)
に書きかえ、i[0],i[1],[2]の代わりにi%30,i/30%30,i/900を使う
(この3数には重複や0が含まれるが影響はない)
……と思ったけど、0~30という5bitの情報しか無いんだからもうちょっと簡単に
for(i=1;i<1<<15;i++)
としてi[x]の代わりに(i>>5*x)&31を使う
(こんどは31も含まれることになるが、31の板を使うことはありえないので、これも影響はない)
更に、入力として考えられるもの30^4通りを全て確かめたところ、出力は最大で9にしかならない
なので初期値の文字数も削減

d[70],a[4],i=1<<15,j,m=9;
main(t){
	for(;~scanf("%d",a+j++););
	for(;--i;){
		for(t=70;--t;d[t]=9);
		for(t=0;t<31;t++)for(j=3;j--;)d[t+(i>>5*j&31)]>d[t]?d[t+(i>>5*j&31)]=d[t]+1:0;
		for(t=j=0;j<4;t+=d[a[j++]]);
		m=m>t?t:m;
	}
	j=!printf("%d",m);
}

出力が1文字ならputcharすればよくね?

d[70],a[4],i=1<<15,j,m=57;
main(t){
	for(;~scanf("%d",a+j++););
	for(;--i;){
		for(t=31;--t;d[t]=9);
		for(;t<31;t++)for(j=3;j--;)d[t+(i>>5*j&31)]>d[t]?d[t+(i>>5*j&31)]=d[t]+1:0;
		for(;++j<4;t+=d[a[j]]+4);
		m=m>++t?t:m;
	}
	j=!putchar(m);
}

DPしてるfor文を抜けたところでt=31になっているので
実際の和+4を加算していくことで、真値+47が保存される
最後にダメ押しの前置incで0のとき48になるようにつじつまを合わせる

ところでループの終わりの時点ではt>31なのに、またt=31をセットするのは冗長だよなあ
最初の1回さえ乗り切れば1B縮みそう
初期値を与えるためにtとjを入れ替えてみる

d[99],a[5],i=1<<20,t=31,m=57;
main(j){
	for(;~scanf("%d",a+j++););
	for(;--i;){
		for(;--t;d[t]=9);
		for(;t<31;t++)for(j=4;--j;)d[t+(i>>5*j&31)]>d[t]?d[t+(i>>5*j&31)]=d[t]+1:0;
		for(;++j<5;t+=d[a[j]]+4);
		m=m>++t?t:m;
	}
	t=!putchar(m);
}

jの初期値が1になったせいでaの読み込みが1個ずれ、
iを5つシフトしたため時間が32倍かかるようになったけどまだ余裕
dの初期化をするときのtの値は最大で48+4*9=84になるのでdのサイズを大きくした
あと代入のところ長いからポインタ使おう

d[99],a[5],i=1<<20,t=31,m=57,*p;
main(j){
	for(;~scanf("%d",a+j++););
	for(;--i;){
		for(;--t;d[t]=9);
		for(;t<31;t++)for(j=4;--j;)*(p=d+t+(i>>5*j&31))>d[t]?*p=d[t]+1:0;
		for(;++j<5;t+=d[a[j]]+4);
		m=m>++t?t:m;
	}
	t=!putchar(m);
}

ループ圧縮

d[99],a[5],i=1<<20,t=31,m=57,*p;
main(j){
	for(;~scanf("%d",a+j++););
	for(;--i;m=m>++t?t:m){
		for(;--t;d[t]=9);
		for(;--j?*(p=d+t+(i>>5*j&31))>d[t]?*p=d[t]+1:1:(j=4*(++t<31)););
		for(;++j<5;t+=d[a[j]]+4);
	}
	t=!putchar(m);
}

ループ終了時のtの値を32にできるようになった やったね

d[99],a[5],i=1<<20,t=31,m=57,*p;
main(j){
	for(;~scanf("%d",a+j++););
	for(;--i;m=m>t?t:m){
		for(;--t;d[t]=9);
		for(;--j?*(p=d+t+(i>>5*j&31))>d[t]?*p=d[t]+1:1:(j=4*(t++<31)););
		for(;++j<5;t+=d[a[j]]+4);
	}
	t=!putchar(m);
}

208B

16/07/15追記
出力でちょっと縮む

d[99],a[5],i=1<<20,t=31,m=57,*p;
main(j){
	for(;~scanf("%d",a+j++););
	for(;--i;m=m>t?t:m){
		for(;--t;d[t]=9);
		for(;--j?*(p=d+t+(i>>5*j&31))>d[t]?*p=d[t]+1:1:(j=4*(t++<31)););
		for(;++j<5;t+=d[a[j]]+4);
	}
	t=!puts(&m);
}

206B