読者です 読者をやめる 読者になる 読者になる

SRM461 Div1Easy ColoringRectangle

解法
直径を大きい順にソートして(1)r,b,r,b,... or (2)b,r,b,r,...の順で貪欲でつめる。red or blue の要素で直径が H 以上のものが尽きたら -1 を出力。そうでなければ長方形の残りの幅を越えた時点で最適。(1)と(2)の小さい方が答え。

class ColoringRectangle {
public:
   int chooseDisks( int width, int height, vector <int> red, vector <int> blue ) {
     
     sort(ALL(red), greater<int>());
     sort(ALL(blue), greater<int>());
     
     double const H = height;
     int ans = red.size()+blue.size()+10;
     
     for(int s=0; s<2; s++) {
       double remain = width;
       
       int flag = s;
       int rcnt = 0, bcnt = 0;
       while(remain > 1e-5) {
	 double d;
	 if(flag==0) {
	   if(rcnt < (int)red.size()) {
	     d = red[rcnt++];
	     if(d < H) goto NEXT;
	   }
	   else goto NEXT;
	 }
	 else {
	   if(bcnt < (int)blue.size()) {
	     d = blue[bcnt++];
	     if(d < H) goto NEXT;
	   }
	   else goto NEXT;
	 }
	 remain -= 2.*sqrt(SQ(d/2) - SQ(H/2));
	 flag = !flag;
       }
       
       ans = min(ans, rcnt+bcnt);
       
     NEXT:;
     }
     
     if(ans > int(red.size()+blue.size())) return -1;
     return ans;
   }
};