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

SRM 602 Div2 Medium PilingRectsDiv2

問題

SRM 602 - TopCoder Wiki

異なる縦幅,横幅をもつ,長方形が複数ある. これらの幾つかの長方形を任意に重ねた時の,全ての長方形とオーバーラップする面積がlimit以上にした時,使用できる長方形の最大数を答えよという問題.

解答

  • 最小幅を固定してから条件に合う長方形の数をカウント.
  • 最小幅を変化させ最適解を探す.
  • 解説よりも冗長なので気をつけよう.
class PilingRectsDiv2
{
public:
  int getmax(vector <int> X, vector <int> Y, int limit)
    {
      int n = X.size();
      int maxx = 0;
      int maxy = 0;
      for (int i = 0 ; i < n; i++) {
        int countx = 0;
        int county = 0;
        for (int j = 0; j < n; j++) {
          if ((X[i] <= X[j] && X[i] * Y[j] >= limit) ||
              (X[i] <= Y[j] && X[i] * X[j] >= limit)) countx++;
          if ((Y[i] <= Y[j] && Y[i] * X[j] >= limit) ||
              (Y[i] <= X[j] && Y[i] * Y[j] >= limit)) county++;
        }
        maxx = max(maxx, countx);
        maxy = max(maxy, county);
      }
      if (maxx == 0 && maxy == 0) return -1;
      return max(maxx, maxy);
    }
};