Moo University - Team Tryouts(2)

Moo Universityは3問あるみたいなので、タイトルを少し変更。さて、昨日の日記にhinoeさんがコードを提供してくれたわけだが、形としては私が目標にしているものに近い。が、探索が不十分だ。

if(w[j]<wmin)

{

  wm=w[j];f=0;

}
if(a*(h[j]-hmin)+b*(w[j]-wm)<=c)

{

  wmin=wm;j=f?j:-1;cnt=++cnt*f;

}

else if(j==i)

{

  wmin=w[i];j=-1;cnt=0;wmm=wm;

}

探索アルゴリズムの大切な部分だが、現在のwminを下回り、かつA*(H-h)+B*(W-w)<=Cを満たす場合はwminを置き換え、ループの最初に即戻っている。これだとそれまでのwminを使った探索を打ち切ったことになる。しかもこれらのデータはwに関して昇順にソートされていないので、wminを下回ったからと言ってもその先にはwminを下回る要素はたくさんあるわけだから、これ（ wm < x < wminを満たすx）も見逃すことになる。

実は前者の問題が結構ネックになって、うまくいっていない。後者の問題は、私が今まで考えていたものとhinoeさんのものを組み合わせて解決することが出来る。コードは後で掲載するが、後者の問題を解決した時点で約800ms(PKU Online上)さらに探索するとなると、Time Limitがまたもや迫ってくる。しかしこの辺りはソートの仕方である程度誤魔化せる可能性もあるので、なんとかなるかもしれない。

探索の精度は少しずつ上がっている。これから進行状況やテストデータ等を公開していくので、皆さんの知恵を貸してくださいっ！！