Topcoder Open Round.2B

結果

o--(+0/-0) 184.32pts 444th
1671->1705(+34)

Highest更新、1700台にのりました。
300-550-900とか0完フラグだろ…と思ったものの
300が解けてよかった。

300

場合分けでガンガン。
0がないときは明らか、
0がk個あるとするとき、
k箇所に1本ずつ当てたとき
(その平均が、既に解っている点数の最大より大きい||解っている数値がない)
場合はk本1セットとして取っていけばよい。

1セットに満たない点数については
0の場所にk本未満投げたときは、少なくとも
(板に存在しない数の小さい方からk個の和)点は取れる。
その平均が既に解っている点数の最大より低ければ
残りの点数は0に当てる必要はなく、解っている点数にあてればよい。

sampleがそこそこ強いと思ったんだけどそうでもなかったようだ。

以下ソース

     int minThrows(vector <int> points, int P) {
         int n = points.size();
         bool isexist[n+1];
         int maxi = -1;
         memset(isexist, false,sizeof(isexist));
         for(int i=0;i<n;i++){
             isexist[points[i]] = true;
             if(points[i] != 0){
                 maxi = max(maxi, points[i]);
             }
         }

         if(isexist[0] == false){
             return (int)ceil((double)P/maxi);
         }else{
             vector<int> cands;
             vector<pair<double,int> > v;
             int sum=0;
             for(int i=1;i<=n;i++){
                 if(!isexist[i]) cands.push_back(i);
             }
             
             for(int i=0;i<cands.size();i++){
                 sum += cands[i];
                 v.push_back(make_pair((double)sum / (i+1),sum));
             }
             if(maxi - v.back().first > -EPS){
                 return (int)ceil((double)P/maxi);
             }

             int ret = 0;
             int set = P / v.back().second;
             P -= v.back().second * set;
             if(P == 0) return set * v.size();
             for(int i=0;i<v.size();i++){
                 if(P <= v[i].second){
                     if(maxi == -1){
                         return set*v.size() + i + 1;
                     }else{
                         return min(set*v.size() + (int)ceil((double)P/maxi), set*v.size() + i + 1);
                     }
                 }
             }
         }
     }