Hatena::Grouptopcoder

tsubosakaの日記

2010-02-14

SRM 461

04:22

120.11/-/-, +50で232位でRateは1816->1826に微増

300

問題の意味がよく分からず500の方に逃げたけどそっちも分からなかったので戻ってといたせいで大幅に得点を落とした。

結局青、赤もしくは赤、青の順で交互に円を置いていって長方形を覆えるかを見ればよく、順番に関しては大きい円から試せば良い。

import java.util.*;

public class ColoringRectangle {
  final static int INF = 1 << 28;
  int placement(int width , int height , int[] b0 , int[] b1){
    int i = b0.length - 1;
    int j = b1.length - 1;
    int k = 0;
    double left = 0.0;
    int cnt = 0;
    for( ; ; ){
      int r;
      if(k == 0){
        if(i < 0)return INF;
        r = b0[i--];
      }else{
        if(j < 0)return INF;
        r = b1[j--];
      }
      if(r < height){
        return INF;
      }
      cnt++;
      left += Math.sqrt(r * r - height * height);
      if(left >= width)return cnt;      
      k = 1 - k;
    }
  }
  
  public int chooseDisks(int width, int height, int[] red, int[] blue) {
    Arrays.sort(red); Arrays.sort(blue);
    int p1 = placement(width, height,  red, blue);
    int p2 = placement(width, height, blue,  red);
    int res = Math.min(p1, p2);
    return res == INF ? -1 : res;
  }
}

Challenge

全部の置き方を試していた人がいたので最大サイズのテストケースを投げてTLEさせる。+50