SRM331Div2

250

vector<string> cat(vector<string> v[], int size)
{
  vector<string> u;
  for(int i=0; i<size; ++i){
    string s;
    for(int j=0; j<v[i].size(); ++j){
      if( s.size() ) s += ' ';
      s    += v[i][j];
    }
    u.push_back( s );
  }
  return u;
}

class SantaGifts {
public:
  vector <string> distribute(vector <string> g, int N) {
    vector <string> r[N];

    for(int i=0, j=0; i<g.size(); ++i){
      if( r[j].size() == 4 ){
        int k = j;
        while( 4 <= r[j].size()){
          j = (j + 1) % N;
          if( j == k )return cat(r, N);
        }
      }
      r[j].push_back( g[i] );
      j = (j + 1) % N;
    }

    return cat(r, N);
  }
};

500

 class CarolsSinging {
public:
  int choose(vector <string> l) {

    const int SONG = l[0].size();
    const int bit = 1 << SONG;

    int mn = 1 << 24;

    for(int i=1; i<bit; ++i){
      int cnt = 0;
      bool vis[l.size()];
      fill( vis, vis + l.size(), false );

      for(int j=0; j<SONG; ++j){
    if( i & (1 << j) )++cnt;
        else continue;

        for(int k=0; k<l.size(); ++k){
          if( l[k][j] == 'Y' )vis[k] = true;
        }
      }

      if( count(vis, vis + l.size(), true) == l.size() ){
        mn = min(mn, cnt);
      }
    }

    return mn;
  }
};

1000
時間がかかった。

lli f[11];

lli rec(int h, int r, int g, int b, int N)
{
  if(r < 0 || g < 0 || b < 0)return 0;
  if( N == h )return 1;

  lli sum = 0;

  int n    = (h + 1);

  if(n % 2 == 0){
    lli m = f[n] / f[n/2] / f[n/2];
    sum += rec(h+1, r - n/2, g - n/2, b, N) * m;
    sum += rec(h+1, r, g - n/2, b - n/2, N) * m;
    sum += rec(h+1, r - n/2, g, b - n/2, N) * m;
  }

  if(n % 3 == 0){
    lli m = f[n] / f[n/3] / f[n/3] / f[n/3];
    sum += rec(h+1, r - n/3, g - n/3, b - n/3, N) * m;
  }

  sum += rec(h+1, r-n, g, b, N);
  sum += rec(h+1, r, g-n, b, N);
  sum += rec(h+1, r, g, b-n, N);

  return sum;
}

class ChristmasTree {
public:
  long long decorationWays(int N, int R, int G, int B) {
    f[0] = 1;
    for(int i=1; i<11; ++i){
      f[i] = f[i-1] * i;
    }
    return rec(0, R, G, B, N);
  }
};