SRM680 div1 easy BearFair - ferinの競プロ帳

考えたこと

題意がよくわからないのでサンプルを試していると[1,upTo[i]]の要素がquantity[i]個存在するということらしい
区間でソートしておくとよさそう
dp[i][j] = (i個目のhintまでの区間で偶数をj個使うのが可能か) みたいなDPを考える
状態数O(nq)、偶数が足される数は多くてもb個くらいっぽいので遷移O(b)で問題なさそう
i個目の区間で偶数を増やせる数について考えるとmin(区間の幅, 偶数の数)になりそう
配るDPを書いてみる
サンプルで落ちてちょっと考え直すと偶数を増やさないといけない下限がある
全部奇数を取っても足りないみたいなパターンになるはずで (区間の幅) - (奇数の数) になる
sample2 みたいに取る要素数がそもそもnに満たないような場合をはじくことにして投げると落ちた
与えられるhintが [1,b] を全てカバーしていない場合が抜け落ちていた…
このケースに対応して投げると通った

DPの遷移とかでかなり混乱した && コーナーケース(?)を見落としてたのが反省点 DPの遷移で詰まったところで実装から紙で整理するのに戻るべきだった

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#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 PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

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); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

class BearFair {
   public:
   string isFair(int n, int b, vector <int> up, vector <int> qua)
  {
    // dp[i][j] = (i番目のhintまででj個偶数を使うような取り方が可能か)
    bool dp[55][55] = {};
    int q = up.size();
    vector<PII> v(q);
    REP(i, q) v[i] = {up[i], qua[i]};
    sort(ALL(v));

    // hintで与えられてない最後の部分について
    if(v.back().first != b && v.back().second != n) v.PB({b, n});

    // hintが要素数の条件に矛盾
    if(v.back().second != n) return "unfair";

    // [prev, v[i].first] について考えるような遷移
    int prev = 1;
    dp[0][0] = true;
    REP(i, v.size()) {
      // 条件に矛盾
      if(i && v[i].second < v[i-1].second) return "unfair";
      // 足せる数 [prev,v[i].first]の偶数の数
      int tmp;
      if(prev%2 || v[i].first%2) tmp = (v[i].first-prev+1)/2;
      else tmp = (v[i].first-prev+1)/2 + 1;
      chmin(tmp, v[i].second-(i==0?0:v[i-1].second));
      // 足さないと行けない数 (区間の幅)-(奇数の数)
      int r = v[i].second-(i==0?0:v[i-1].second) - (v[i].first-prev+1-tmp);
      chmax(r, 0);
      // 配るDP
      REP(j, n) if(dp[i][j]) {
        FOR(k, r, tmp+1) dp[i+1][j+k] = true;
      }
      // 区間について更新
      prev = v[i].first + 1;
    }

    if(dp[v.size()][n/2]) return "fair";
    return "unfair";
  }
};