SRM305Div2

250

class MultiRead {
public:
  int minCycles(string t, int p) {
    string s;
    for(int i=0; i<t.size(); ++i){
      if( t[i] == 'W' )s += '@';
      else{
        int cnt = 0;
        while(i < t.size() && t[i] == 'R'){
          ++cnt;
          ++i;
        }
        --i;
        int l = cnt / p + (bool)(cnt % p);
        for(int j=0; j<l; ++j){
          s += '@';
        }       
      }
    }   
    return s.size();
  }
};

500
問題文の読解も含めて、とても時間がかかった。

class UnfairDivision {
public:
  int albertsShare(vector <int> v) {
    int r = 0;
    for(int i=1; i<v.size(); ++i){
      int s = (1 << 24);
      int t = 0;
      for(int j=1; j<v.size(); ++j){
        if(i == j)continue;
        int sum[3];
        int idx = 0;
        sum[0] = sum[1] = sum[2] = 0;
        for(int k=0; k<v.size(); ++k){
          if(k == i || k == j)++idx;
          sum[idx] += v[k];
        }
        sort(sum, sum + 3);
        if(t < sum[1]){
          t = sum[1];
          s = sum[0];
        }
        else if(t == sum[1])s = min(s, sum[0]);
      }
      if(s != (1 << 24))r = max(r, s);
    }
    return r;
  }
};

1050
もっと簡素に描けるようにしたい。

const int N = 100 + 1;

struct S{
  int m, c, b;
  S(){}
  S(int _m, int _c, int _b){
    m = _m;
    c = _c;
    b = _b;
  }
};

class Cannibals {
public:
  int minCrossings(int M, int C, int R) {
    bool vis[N][N][2];
    int w[N][N][2];
    fill( &vis[0][0][0], &vis[N-1][N-1][2], false );
    fill( &w[0][0][0], &w[N-1][N-1][2], -1 );
    vis[M][C][0] = true;
    w[M][C][0] = 0;
    queue<S> q;    
    int m1, c1, m2, c2, b;
    for(q.push( S(M, C, 0) ); q.size(); q.pop()){
      S s = q.front();
      b = s.b ^ 1;
      if(s.b){
        for(int i=0; i<=M-s.m; ++i){
          for(int j=0; j<=C-s.c; ++j){
            if(i == 0 && j == 0)continue;
            if(R < i + j)continue;
            if(i && i < j)continue;
            m1 = s.m + i;
            c1 = s.c + j;
            m2 = M - m1;
            c2 = C - c1;
            if( vis[m1][c1][b] )continue;
            if(m1 && m1 < c1)continue;
            if(m2 && m2 < c2)continue;
            w[m1][c1][b] = w[s.m][s.c][s.b] + 1;
            vis[m1][c1][b] = true;
            q.push( S(m1, c1, b) ); 
          }
        }
      }
      else{
        for(int i=0; i<=s.m; ++i){
          for(int j=0; j<=s.c; ++j){
            if(i == 0 && j == 0)continue;
            if(R < i + j)continue;
            if(i && i < j)continue;
            m1 = s.m - i;
            c1 = s.c - j;
            m2 = M - m1;
            c2 = C - c1;
            if( vis[m1][c1][b] )continue;
            if(m1 && m1 < c1)continue;
            if(m2 && m2 < c2)continue;
            w[m1][c1][b] = w[s.m][s.c][s.b] + 1;
            vis[m1][c1][b] = true;
            q.push( S(m1, c1, b) ); 
          }
        }
      }
    }
    return w[0][0][1];
  }
};