Sticks(10)

最短コード250B

270byteあたりからは、ロベールさんと私でじわりじわりと削り合い。ちなみに、前回までで紹介しているコードは、はてな用に私が新しく書きなおしたものなので当時のコードとは違う部分もある。どんなインプットでも通るコードというのは、実は260byteくらいまでしか短縮することが出来ない。それ以上縮めるには探索時間やメモリを犠牲にしていかなければならないのだ。

260byte程まで縮んだところで、ロベールさんがTLE(Time Limit Exceed)に掛からない程度に探索ループを書き換え254byte。そして私がそこからさらに短縮して251byte。

L,F,*I;
c(n,l,p,j){

 --I[p];

 for(j=l-=p;F*j;--j)I[j]&&c(n,l,j);

 for(j=F=--n?F:0;!I[j];)--j;l||c(n,L,j);

 ++I[p];

}
main(s){

 int w[999]={s=F};

 for(scanf("%d",I=w);w[0]--;++w[L],s+=F<L?F=L:L)scanf("%d",&L);

 for(L=F-1;F;s%++L||c(s/L,L,F));s&&main(printf("%d\n",L));

}

私は「これでホントに終わりっ！」と思ったのだが、またしてもやられた。上記のコード上で

w[0]--

と書いてある部分。私は、w[0]--と書いても(*w)--と書いても文字数が変わらないので、冗長だと感じながらも諦めていた。

しかしロベールさんはこんな書き方で見事1byte縮めてしまった。

~--*w

スゴイ。

というわけで最短コード250byteはまたしてもロベールさんにやられてしまった。しかし私はいつも2位じゃイヤだ。なんとか一番上に載りたい。

というわけでこのようなコードを書いた。

L,F,*I;
c(n,l,p,j){

 --I[p];

 for(j=l-=p;F*j;--j)I[j]&&c(n,l,j);

 for(j=F=--n?F:0;!I[j];)--j;l||c(n,L,j);

 ++I[p];

}
main(s){

 int w[101]={s=F};

 for(scanf("%d",I=w);~--*w;++w[L],s+=F<L?F=L:L)scanf("%d",&L);

 for(L=F-1;F;s%++L||c(s/L,L,F));s&&main(printf("%d\n",L));

}

変更点は配列のサイズのみ。この問題のテストケースでは、配列番号のサイズが最大でも100であることを調べて101としておいた。これでメモリ消費量を1088kから180kまで減らすことが出来る。もう他には何も思いつかない。

っちゅうことで最短コードは250B！