SRM322Div2

ここ何回かで解いた問題は、1000より500の方が難しい気がする。


250

class DerivativeSequence {
public:
  vector <int> derSeq(vector <int> a, int n) {
    vector <int> r = a;
    while( n-- ){
      r.clear();
      for(int i=0; i+1<a.size(); ++i){
        r.push_back( a[i+1] - a[i] );
      }
      a = r;
    }
    return r;
  }
}; 

500
悩んだ。

class GroupWork {
public:
  long long bestGroup(vector <int> p, vector <int> s) {
    const int size = p.size();
    lli r = 1;
    for(int i=0; i<size; ++i){
      lli sum = 0;
      for(int j=0; j<size; ++j){
        if( s[i] <= s[j] ) sum += p[j];
      }
      r = max(r, sum * s[i]);
    }
    return r;
  }
};

1000

class BattleshipChecker {
public:
  string checkBoard(vector <string> b) {
    const string R = "REJECTED";
    int sum = 0;
    const int h = b.size();
    const int w = b[0].size();
    for(int i=0; i<h; ++i){
      sum += count( b[i].begin(), b[i].end(), 'X' );      
    }
    if(sum != 1*4 + 2*3 + 3*2 + 4*1)return R;
    
    int p = 0;
    for(int i=0; i<h; ++i){
      p += count( b[i].begin(), b[i].end(), 'X' ) == 0;
    }
    for(int j=0; j<w; ++j){
      int cnt = 0;
      for(int i=0; i<h; ++i){
        cnt += b[i][j] == 'X';
      }
      p += cnt == 0;
    }


    bool vis[h][w];
    fill( &vis[0][0], &vis[h-1][w], false );

    int ship[5];
    ship[0] = 0;
    ship[1] = 4;
    ship[2] = 3;
    ship[3] = 2;
    ship[4] = 1;

    for(int i=0; i<h; ++i){
      for(int j=0; j<w; ++j){
        if( b[i][j] != 'X' )continue;
        int di[] = {-1, -1, 1, 1};
        int dj[] = {-1, 1, -1, 1};        
        for(int d=0; d<4; ++d){
          int ni = i + di[d];
          int nj = j + dj[d];
          if( ni < 0 || nj < 0 )continue;
          if( h <= ni || w <= nj )continue;
          if( b[ni][nj] == 'X' )return R;
        }
        if( vis[i][j] )continue;
        int s, t;
        for(s = 0; ; ++s){
          if(h <= i+s)break;
          if( b[i+s][j] != 'X' )break;
          vis[i+s][j] = true;
        }
        for(t = 0; ; ++t){
          if(w <= j+t)break;
          if( b[i][j+t] != 'X' )break;
          vis[i][j+t] = true;
        }
        if( s-1 && t-1 )return R;
        int size = max(s, t);
        if(4 < size)return R;
        --ship[ size ];
      }
    }

    if( count( ship, ship + 5, 0 ) == 5 ){
      char buff[100];
      sprintf(buff, "ACCEPTED, %d POINTS", p);
      return string(buff);
    }
    else return R;
  }
};