codeforces #428 div2 B. Game of the Rows

問題ページ
Problem - B - Codeforces

考えたこと

• 二人席が2n個、四人席がn個あると考えればよさそう
• ぴったり座れるときに座らない方がいいことはなさそう
• 二人席と四人席のどちらを先に埋めるべきか
• 四人席*1より二人席*2の方があとあとぴったり埋められるのが増えそうだし四人席を先に埋めるべきっぽい
• 4人席を埋められるだけ埋めたあと2人席を埋めるみたいなのを書く
• sampleを見ると2人席が埋まって4人席が空いてるときに4人以下が来るみたいなパターンがある
• 4人席に2人を座らせたら4人席が減って1人席が増えると考えることにした
• 4人席を埋められるだけ埋める
  • 4人席が残っていたらそのグループの残り人数は3人以下 (ピッタリ埋められる) > (4人席) > (2人席) > (1人席) の優先度で埋める
  • 4人席が残っていなかったら2人席で埋める
• 出したら落ちる
• コーナーケースが無限にありそうだけど見つからない
  -----解説を見た-----
• 2人を1人席2つで座らせる場合が抜けていた…
• 4の倍数人は絶対にぴったり座らせられる
• 各グループで人数が3人以下になるまで座らせておく
• a[i] = 1, a[i] = 2, a[i] = 3 で場合分けして座らせる

コーナーケースになりそうなのとして下のとか

3 11
2 2 2 2 2 2 2 2 2 2 2

C - スキーリフトの相乗りを思い出した
場合分けゲー苦手すぎる

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
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};

signed main(void)
{
  int n, k;
  cin >> n >> k;
  int two = n*2, four = n, one = 0;
  VI a(k);
  REP(i, k) cin >> a[i];

  // a[i]で4以上の分を埋める
  REP(i, k) {
    if(four > a[i]/4) {
      four -= a[i]/4;
      a[i] %= 4;
    } else {
      a[i] -= four*4;
      four = 0;
    }

    if(a[i] < 4) continue;
    two -= a[i]/2;
    a[i] %= 2;
  }

  // 各グループは4人以下
  REP(i, k) {
    if(a[i] == 3) {
      if(one >= 3) one -= 3;
      else if(four) four--;
      else if(two >= 2) two -= 2;
      else {
        cout << "NO" << endl;
        return 0;
      }
    } else if(a[i] == 2) {
      if(two) two--;
      else if(four) four--, one++;
      else if(one >= 2) one -= 2;
      else {
        cout << "NO" << endl;
        return 0;
      }
    } else if(a[i] == 1) {
      if(one) one--;
      else if(four) four--, two++;
      else if(two) two--;
      else {
        cout << "NO" << endl;
        return 0;
      }
    }
  }
  cout << "YES" << endl;

  return 0;
}