SRM629 div1 easy RectangleCovering

概要

holeH、holeWの大きさの穴を複数の板を使って塞ぐ。板iの大きさはboardH[i]、boardW[i]である。板は重なっても良いが全ての角が穴の外に位置していなければならない。このとき塞ぐのに必要な最小枚数を答えろ。不可能なら-1を答える。

解法

holeH >= boardH && holeW >= boardW の板を使用することはできないので無視する。
holeHより一辺が大きい板を使って穴をふさいでいくとき、板が足りずふさぎきれなかったとする。このときまだ空いている穴を塞ぐには、holeWより一辺が大きい板を使用してふさぐ必要がある。しかし、holeWより一辺が大きい板でふさげるのであればholeHより一辺が大きい板を使用する必要はない。したがって、holeHより一辺が大きい板のみでふさぐか、holeWより一辺が大きい板のみでふさぐかの2パターンで独立に考えられる。
それぞれ、条件を満たす板を列挙しておきより広い範囲をふさげる板から貪欲に使用していけばよい。sortが一番時間がかかっていてO(nlogn)で計算できる。

最初 holeH+1 < max(boardH, boardW) がふさげる板の条件かと思ったけどサンプルが合わなくて悩んだ。よくよく考えると格子点上だけに板の角を配置できるわけじゃなさそう。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class RectangleCovering {
   public:
   int minimumNumber(int holeH, int holeW, vector <int> boardH, vector <int> boardW)
  {
    int n = boardH.size();
    vector<PII> v1, v2;
    REP(i, n) {
      if(boardH[i] > holeH && boardW[i] > holeH) {
        v1.PB({max(boardW[i], boardH[i]), min(boardW[i], boardH[i])});
      } else if(boardH[i] > holeH) {
        v1.PB({boardW[i], boardH[i]});
      } else if(boardW[i] > holeH) {
        v1.PB({boardH[i], boardW[i]});
      }

      if(boardH[i] > holeW && boardW[i] > holeW) {
        v2.PB({max(boardW[i], boardH[i]), min(boardW[i], boardH[i])});
      } else if(boardH[i] > holeW) {
        v2.PB({boardW[i], boardH[i]});
      } else if(boardW[i] > holeW) {
        v2.PB({boardH[i], boardW[i]});
      }
    }
    sort(ALL(v1)); sort(ALL(v2));
    reverse(ALL(v1)); reverse(ALL(v2));

    ll now = 0, ans = LLINF;
    REP(i, v1.size()) {
      now += v1[i].first;
      if(now >= holeW) {
        ans = i+1;
        break;
      }
    }
    now = 0;
    REP(i, v2.size()) {
      now += v2[i].first;
      if(now >= holeH) {
        chmin(ans, i+1);
        break;
      }
    }
    return ans == LLINF ? -1 : ans;
  }
};