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

メモ

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

yukicoder No.5 数字のブロック

問題はこちら
No.5 数字のブロック - yukicoder

ソートして小さい方から使っていく

int c(int*a,int*b){return*a-*b;}
int main(){
	int w[10001]={},i,j,l;
	scanf("%d%d",&l,&n);
	for(i=0;i<n;i++)scanf("%d",w+i);
	qsort(w,n,4,c);
	i=j=0;
	while(i<=l&&j<=n)i+=w[j++];
	//あふれるまでいれて1個引く。w[n]は0
	printf("%d",j-1);
	return 0;
}

L,Nもまとめて配列に読み込むことにして短縮

i,j=2,w['~~'];
c(int*a,int*b){i=*a-*b;}
main(){
	for(;~scanf("%d",w+i++););
	qsort(w+2,w[1],4,c);
	//qsortのコールバック関数内でiを使ったのでqsort(w+2,i-3,4,c)だとバグる
	for(i=0;i<=*w&&w[j];)i+=w[j++];
	j=!printf("%d",j-3);
}

さらに箱詰めチェックを次のように1ずつすることで短縮
(全く同じ問題であるNo.156 キャンディー・ボックス - yukicoderを考えている時に思いついた)

i,j,w['~~'];
c(int*a,int*b){i=*a-*b;}
main(){
	for(;~scanf("%d",w+i++););
	for(qsort(w+2,w[1],4,c);w[0]--;j+=!--w[j+2]);
	//今見ているブロックが、箱に入りきった瞬間にjがincされるので、
	//結局jには「既に入れることが出来た箱の数」が保存されることになる
	//※w[0]--は*w--とは書けない(*(w--)と解釈されCE)
	j=!printf("%d",j);
}

ループ圧縮
ちなみにw[0]--は~--*wと書ける

i,w['~~'];
c(int*a,int*b){i=*a-*b;}
main(j){
for(;!~scanf("%d",w+i++)?qsort(w+2,w[1],4,c),~--*w?j+=!--w[j+1]:!printf("%d",j-1):1;);
}

ここでわざわざjをmain第一引数にしたのはj+=!--w[j+1]を常に非0にするため。
そのままにするより1B得
以上129B

なお、yukicoderの環境でも、qsortのコールバック関数hackはできるらしい
#21775 No.190 Dry Wet Moist - yukicoder
ぼくにはとてもできない