Sticks(7)

計算量を減らす

ちょっとした演算でも数十万回呼ばれる可能性があるのであれば、それなりに時間がかかってしまう。演算回数を減らす努力は、再帰の仕組みを真面目に考えるきっかけになり、コードはスマートになっていく。そして、最終的にはコード短縮につながる。
昨日のコードで無駄な部分は、in[n]のデクリメント・インクリメントを2箇所で行っている点。再帰なら一度ずつで済むはずだ。

ということを考えて修正すると、700byte弱になった。シンボル名を一文字にして改行コードを除けば半分程度になるだろうから、これを短縮すればおそらく300byteくらいにできるだろう。

int length,finish,in[51];
check(count, len, plen)

{

 int j;

 --in[plen];

 if(count==0)finish=1;

 if(!finish){

  if(len-=plen){

   for(j=len<plen?len:plen; j>0; --j){

    if(in[j])check(count, len, j);

   }

  } else {

   for(j=51;!in[j];)--j;

   check(count-1, length, j);

  }

 }

 ++in[plen];

}
main()

{

 int b,sum,max;

 while(~scanf("%d",&in[0])){

  if(in[0]==0)break;

  sum=0;max=0;finish=0;

  for(;in[0]--;){

   scanf("%d",&b);

   ++in[b];

   sum+=b;

   if(max<b)max=b;

  }

  for(length=max; !finish ; ++length){

   if(sum%length==0)check(sum/length,length,max);

  }         

  printf("%d\n",length-1);memset(in, 0, 4*51); 

 }

}