解いた問題

7/03/2011

SRM453Div2

250
class TheTournamentDivTwo {
public:
  int find(vector <int> points) {

    int ret = 0;

    for(int i=0; i<points.size(); ++i){
      ret += points[i] / 2;
      points[i] %= 2;
    }
    
    int sum = accumulate( points.begin(), points.end(), 0 );
    if( sum % 2 )return -1;

    return ret + sum / 2;
  }
};
500
class TheBasketballDivTwo {
public:
  int find(vector <string> t) {

    string s;
    for(int i=0; i<t.size(); ++i) s += t[i];

    const int inf = 1 << 25;
    const int N = t.size();
    const int BIT = 1 << (N * N - N);

    int mn = inf;
    
    char g[N][N];
    for(int bit = 0; bit < BIT; ++bit){
      
      for(int i=0, k=0; i<N; ++i){
        for(int j=0; j<N; ++j){
          if( i == j )g[i][j] = 'X';
          else g[i][j] = ( bit & ( 1 << k++ ) )? 'W' : 'L';
        }        
      }     

      int mx = 0;
      for(int i=0; i<N; ++i){
        int cnt = 0;
        for(int j=0; j<N; ++j){
          if( i != j ){
            cnt += g[i][j] == 'W'; 
            cnt += g[j][i] == 'L'; 
          }
        }
        mx = max( mx, cnt );
      }

      bool flg = true;
      for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
          if( t[i][j] == '?' )continue;
          if( t[i][j] == g[i][j] )continue;          
          flg = false;
          i = j = N;
        }
      }
      
      if( flg )mn = min( mn, mx );
    }

    return mn;
  }
};
1000
面倒だった。時間がかかった。投げ出したかった。
class TheSoccerDivTwo {
public:
  int find(vector <int> p) {

    const int size = p.size();
    bool fin[size];

    fill( fin, fin + size, false );

    p[0] += 3;
    fin[0] = true;
    
    for(int i=1; i<size; ++i){
      for(int j=1; j<size; ++j){
        if( i == j || fin[i] || fin[j] )continue;
        if( p[i] + 1 <= p[0] && p[i] + 3 > p[0] ); else continue;
        if( p[j] + 1 <= p[0] && p[j] + 3 > p[0] ); else continue;
        fin[i] = fin[j] = true;
        p[i] += 1;
        p[j] += 1;
      }
    }

    for(int i=0; i<size; ++i) printf( (fin[i] ? "  x" : "  -" ) ); puts("");
    for(int i=0; i<size; ++i) printf("%3d", p[i]); puts("");

    for(int i=1; i<size; ++i){
      for(int j=1; j<size; ++j){
        if( i == j || fin[i] || fin[j] )continue;
        if( p[i] > p[0] || p[i] + 3 <= p[0] ); else continue;
        if( p[j] + 3 > p[0] && p[j] <= p[0] ); else continue;
        fin[i] = fin[j] = true;
        p[i] += 3;
        p[j] += 0;
      }
    }

    for(int i=0; i<size; ++i) printf( (fin[i] ? "  x" : "  -" ) ); puts("");
    for(int i=0; i<size; ++i) printf("%3d", p[i]); puts("");

    for(int i=1; i<size; ++i){
      for(int j=1; j<size; ++j){
        if( i == j || fin[i] || fin[j] )continue;
        if( p[i] + 3 > p[0] ); else continue;
        if( p[j] + 3 > p[0] ); else continue;
        fin[i] = fin[j] = true;
        p[i] += 3;
        p[j] += 0;
      }
    }

    for(int i=0; i<size; ++i) printf( (fin[i] ? "  x" : "  -" ) ); puts("");
    for(int i=0; i<size; ++i) printf("%3d", p[i]); puts("");

    int ret = 0;
    for(int i=1; i<size; ++i){
      if( p[i] > p[0] ) ++ret;
    }

    return ret + 1;
  }
};

0 件のコメント :

コメントを投稿