naoya_t@topcoder

SRM355 Div1 Easy (300points): MixingLiquids

過去問, 練習 | 03:36 |

• なんか線形計画法っぽい
• 最初に考えたやつではテスト通らない
• 横軸にsubstance,縦軸にwater、で生成可能な溶液の範囲を表すconvexと、求める濃度を表す（原点を通る）直線の交点（で原点から一番遠い所）
• convexは左回りが薄い順、右回りが濃い順
• 0%,100%の対策（直線の傾きが∞になっても死なないように）
• 同じ濃度の溶液が複数あった場合の対策（最初にまとめる）
• 求める濃度と同じ濃度の溶液については最初に除外
• など、解き方は分かったんだけど最初にあれこれ試行錯誤した分で時間が足りず。途中トイレに立ったのも入れて1時間半ぐらい。
• 90.0 points (time over), Passed System Test

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())
#include <float.h>

class MixingLiquids {
 public:
  double howMuch(vector<int> percent, vector<int> amount, int need) {
    int n=sz(percent);

    // uniq
    map<int,int> pa_;
    rep(i,n){
      int pi=percent[i],ai=amount[i];
      if(found(pa_,pi))
        pa_[pi] += ai;
      else
        pa_[pi] = ai;
    }

    vector<pair<double,pair<double,double> > > pa;
    double subssum=0.0, watsum=0.0;
    double mixsubs=0.0, mixwat=0.0;
    tr(pa_,it){
      int pi=it->first, ai=it->second;
      double subs=0.01 * ai * pi;
      double wat=(double)ai - subs;
      if(pi==need){
        mixsubs += subs;
        mixwat += wat;
      }else{
        subssum += subs;
        watsum += wat;
        pa.pb(make_pair((subs==0)?DBL_MAX:wat/subs,make_pair(subs,wat)));
      }
    }
    if(subssum==0 || need==0){ // water only
      return mixsubs+mixwat;
    }
    double totalm = watsum/subssum, needm = (double)(100-need)/need;
    if(totalm==needm){
      return (mixsubs+mixwat)+(subssum+watsum);
    }else if(totalm<needm){
      // water左
      sort(all(pa)); reverse(all(pa));
      double x=0,y=0;
      tr(pa,it){
        double m=it->first, s=it->second.first, w=it->second.second;
        double x_=x+s, y_=y+w;
        if(x_==0){
          if(need==0) return (mixsubs+mixwat)+y_;
        } else if (y_/x_ <= needm) {
          if(m==DBL_MAX){
            x_ = x;
          }else{
            x_ = (m*x-y)/(m-needm);
          }
          y_ = x_*needm;
          return (mixsubs+mixwat)+(x_+y_);
        }
        x=x_; y=y_;
      }
      
    }else{
      // subs右
      sort(all(pa));
      double x=0,y=0;
      tr(pa,it){
        double m=it->first, s=it->second.first, w=it->second.second;
        double x_=x+s, y_=y+w;
        if(x_==0){
          if (need==0) return (mixsubs+mixwat)+y_;
        }else if (y_/x_ >= needm) {
          if(m==DBL_MAX){
            x_ = x;
          }else{
            x_ = (m*x-y)/(m-needm);
          }
          y_ = x_*needm;
          return (mixsubs+mixwat)+(x_+y_);
        }
        x=x_; y=y_;
      }
    }
    return (mixsubs+mixwat)+(subssum+watsum);
  }
};