SRM689 div1 easy ColorfulGarden

考えたこと

• 互い違いにおいていくのが一色を多く置く方法っぽい
• 一色でn個より多くあるのを条件を満たすようには置けない
• 逆に全部n個以下なら適当に互い違いにおいていくだけで構成できる

割とすぐ思いつけた

ソースコード

#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); }

ll cnt[30];
class ColorfulGarden {
   public:
   vector <string> rearrange(vector <string> g)
  {
    ll n = g[0].size();
    memset(cnt, 0, sizeof(cnt));
    REP(i, 2) REP(j, n) cnt[g[i][j]-'a']++;

    vector<PII> p;
    REP(i, 26) {
      if(cnt[i] > n) return {};
      p.PB({cnt[i], i});
    }
    sort(ALL(p), greater<PII>());

    vector<PII> v;
    int turn = 0;
    REP(i, n) {v.PB({turn, i}); turn = !turn;}
    turn = 1;
    REP(i, n) {v.PB({turn, i}); turn = !turn;}

    vector<string> ret(2, string(n, 'a'));
    int idx = 0;
    REP(i, 26) {
      while(p[i].first) {
        ret[v[idx].first][v[idx].second] = (char)(p[i].second+'a');
        p[i].first--; idx++;
      }
    }

    return ret;
  }
};