PKU2249まとめ(2)

program

そこで、ここからコードを縮めるためにここにいくつかの驚愕すべきテクニックを投入する。


・int型の変数の宣言をしたくない
使用するint型の変数は2つなのでmainの引数にしてしまう


・このdoubleをfloatに出来ないか
ローカル変数で宣言すれば出来る。これはローカル変数であればレジスタ割付がなされるため、FPUで計算される。その場合、float型なのにdouble型と同じ計算精度を持つ。この発見はkurimuraさんによる。(id:kurimura:20060603)


・ループの終了条件をもっと短くかけないか
nが0の入力が終端にある。rがn以下なのは保証されているからnが0かどうかだけチェックすれば良い。


・a=1の初期化部分を短くできないか？
scanfは正常に取得できた数値の数を返す。入力は2つの整数が組になっているので、常に2を返す関数だと考えて良い。nは最後以外は非0。よって、



a=scanf("%d%d",&n,&r)&&n;

と書くことが出来る。


そんなわけで私が書いた97byteのコードとは



main(n,r){float a;for(;a=scanf("%d%d",&n,&r)&&n;printf("%.f\n",a))for(;r=r>9?n-r:r;)a=a*n--/r--;}

こういうコードだった。r>9 の部分がずるい気はするが、TLEになるのはr=20億という巨大な入力に対してだけだから、そこさえr = n - r になっていればTLEにはならないことを利用している。


・input解析を行なう
これ以上、縮む気配がないので私はinput解析を行なった。



4,2 

5,5 

49,6 

2000000000,0 

2000000000,1 

2000000000,1999999999 

2000000000,2000000000 

65000,2 

65000,64998 

64999,2 

64999,64997

2300,3 

2300,2297 

400,4 

100,5 // i == 14 

ここで気力尽きた。

input解析用のコード。TLEとWAとで真偽を判定するようになっている。



main(n,r){ 

  float a; int i; 

  for(i=0;a=scanf("%d%d",&n,&r)&&n;++i) 

  { 

    // ここ適当にいじるヨロシ 

    if (i==8 && r>=65000){ 

      while(1) ; 

    } else { 

      printf("ABC"); 

    } 
    for(;r=r>9?n-r:r;)a=a*n--/r--; 

    printf("%.f\n",a); 
  } 

}

結局r=20億というのがTLEにさせるための罠のようだ。input値は境界テストなど非常にツボを心得ているという感じの値で、これをごまかしてacceptさせるのは一筋縄ではいかない。正攻法のほうが良さそうだという結論になる。


inputを見て気づくのはnに1,2が含まれていないということである。これにより、a = scanf(...)&&nの部分はa=scanf(..)<nと書けることに気づく。これはOzyさんの発見。


・もう縮まないのか？

この時点で96byte。もう縮む場所はないのだろうと思っていたところにOzyさんが離れ業をやってのけた。90byte。一体どういうコードなんだろう？そのコードとはこれだ。



main(n,r){

  float s;

  for(;s=scanf("%d%d",&n,&r)<n;printf("%.f\n",s))

    for(;r=n-r;)s=s*n--/r--;

}

なんとも巧妙だ。r=n-rがミソである。(id:Ozy:20060604#p1)　私はr=n-rは別の条件のときに試していたのだが、そちらではacceptされなかったので諦めていた。もはや完敗である。90byte。この偉大な記録を打ち破ることは出来るのだろうか？