SRM328Div2

250

class MarbleNecklace {
public:
  string normalize(string n) {
    int size = n.size();
    string s(n.size(), 'Z');
    n = n + n;
    for(int i=0; i<size; ++i){
      s = min(s, n.substr(i, size));
    }
    reverse(n.begin(), n.end());
    for(int i=0; i<size; ++i){
      s = min(s, n.substr(i, size));
    }
    return s;
  }
};

500

class LightsCube {
public:
  vector <int> count(int N, vector <string> l) {
    
    int color[N][N][N];
    fill( &color[0][0][0], &color[N-1][N-1][N], 0 );

    for(int i=0; i<l.size(); ++i){
      istringstream iss( l[i] );
      int a, b, c;
      iss >> a >> b >> c;
      color[a][b][c] = i+1;
    }

    vector<int> v;
    for(int i=0; i<N; ++i){
      for(int j=0; j<N; ++j){
        for(int k=0; k<N; ++k){
          if( color[i][j][k] == 0 ){
            int a = 100 * 100 * i;
            int b = 100 * j;
            int c = k;
            v.push_back( a + b + c );
          }
        }
      }
    }

    while( v.size() ){
      int next[v.size()];
      fill( next, next + v.size(), 0 );
      const int dx[] = {-1, 1, 0, 0, 0, 0};
      const int dy[] = {0, 0, -1, 1, 0, 0};
      const int dz[] = {0, 0, 0, 0, -1, 1};
      for(int i=0; i<v.size(); ++i){
        int cnt = 0;
        int mn = 1 << 24;
        int a = v[i] / (100 * 100);
        int b = v[i] / 100 % 100; 
        int c = v[i] % 100;
        for(int d=0; d<6; ++d){
          int na = a + dx[d];
          int nb = b + dy[d];
          int nc = c + dz[d];
          if(na < 0 || nb < 0 || nc < 0)continue;
          if(N <= na || N <= nb || N <= nc)continue;
          if( color[na][nb][nc] ){
            ++cnt;
            mn = min(mn, color[na][nb][nc]);
          }
        }
        if( cnt )next[i] = mn;
      }
      for(int i=(int)v.size()-1; 0<=i; --i){
        if( next[i] ){
          int a = v[i] / (100 * 100);
          int b = v[i] / 100 % 100;          
          int c = v[i] % 100;
          color[a][b][c] = next[i];
          v.erase( v.begin() + i );
        }
      }
    }

    v.resize(l.size(), 0);
    for(int i=0; i<N; ++i){
      for(int j=0; j<N; ++j){
        for(int k=0; k<N; ++k){
          ++v[ color[i][j][k]-1 ];
        }
      }
    }

    return v;
  }
};

1000

int b[4][4];
int no[4][4];

map<int, int> opt;

int rec(int bit)
{
  if( bit == (1 << 16) - 1 )return 0;
  if( opt.count(bit) )return opt[bit];

  int mx = -(1 << 23);

  for(int i=0; i<4; ++i){
    for(int j=0; j<4; ++j){
      if( bit & (1 << no[i][j]) )continue;
      bool flg = false;
      const int di[] = {-1, 1, 0, 0};
      const int dj[] = {0, 0, -1, 1};
      for(int d=0; !flg && d<4; ++d){
        int ni = i + di[d];
        int nj = j + dj[d];
        if( ni < 0 || nj < 0 )flg = true;
        else if( 4 <= ni || 4 <= nj )flg = true;
        else if( bit & (1 << no[ni][nj]) )flg = true;
      }
      if( flg ){
        mx = max( mx, b[i][j] - rec( bit | (1 << no[i][j]) ) );
      }
    }
  }

  return opt[bit] = mx;
}

class ScoreDifference {
public:
  int maximize(vector <string> board) {

    opt.clear();

    for(int i=0; i<board.size(); ++i){
      istringstream iss( board[i] );
      for(int j=0; j<4; ++j){
        iss >> b[i][j];
      }
    }

    int cnt = 0;
    for(int i=0; i<4; ++i){
      for(int j=0; j<4; ++j){
        no[i][j] = cnt++;
      }
    }
    
    return rec(0);
  }
};