Codeforces Round #115

GCJから連続参加．参加するのは良いけど日記かこうとすると大変だー

Problem A Robot Bicorn Attack

問題

３ラウンドの点数が全部つながった状態で与えられる．
各ラウンドの点数は1000000以下であることがわかっている
合計点としてありえる最大値を返せ．入力が明らかにおかしい場合は-1を返せ

考えたこと

a,bの点数の桁数を指定して前通りやるだけ…って言いつつ1000000以下とか条件色々忘れて時間かかった

コード

int main(){
  string str;
  cin >> str;
  int ans = -1;
  for( int i = 1 ; i < 30 ; i++ ){
    for( int j = 1 ; j < 30 ; j++ ){
      if( i + j >= str.size() ) continue;
      string a = str.substr( 0, i );
      string b = str.substr( i, j );
      string c = str.substr( i+j);
      if( a[0] == '0' && a.size() > 1 ) continue;
      if( b.size() > 1 &&  b[0] == '0' ) continue;
      if( c.size() > 1 && c[0] == '0' ) continue;
      if( a.size() > 7 ) continue;
      if( b.size() > 7 ) continue;
      if( c.size() > 7 ) continue;
      int a_score = atoi( a.c_str() );
      int b_score = atoi( b.c_str() );
      int c_score = atoi( c.c_str() );
      if( a_score > 1000000 ) continue;
      if( b_score > 1000000) continue;
      if( c_score > 1000000 ) continue;
      ans = max( ans, a_score + b_score + c_score );
    }
  }
  cout << ans;
  return 0;
}

Problem B. Plane of Tanks: Pro

問題

人，点数の組合せをひたすら与えるので
参加人数と，各人がnoob, random, average, hardcore, proのどれであるかのリストを返せ．
noob...等の定義は，全体の何割が自分よりも点数が低い，といった形式で与えられる．

考えたこと

これもやるだけ，noobとかの定義をガシガシ考えるのが面倒くさかった．

コード

int main(){
  int n_case;
  cin >> n_case;
  map< string,int> score;
  set<string> player;
  int bunpu[1001];
  int n_player=0;
  memset( bunpu, 0 , sizeof(bunpu) );
  for( int i = 0 ; i < n_case ; i++ ){
    string name;
    int point;
    cin >> name >> point;
    player.insert(name);
    if( (int)player.size() >n_player){
      n_player++;
      score[name] = point;
      bunpu[score[name]]++;
    }else{
     if( score[name] < point ){
      bunpu[score[name]]--;
      score[name] = point;
      bunpu[point]++;
     }
    }
  }
  int now = 0;
  for( int i = 0 ; i <= 1000; i++ ){
    bunpu[i] = now + bunpu[i];
    now = bunpu[i];
  }
  cout << player.size()<<endl;
  int size = n_player;
  set<string>::iterator it = player.begin();
  while( it != player.end() ){
    string nowplayer = *it;
    int nowscore = score[nowplayer];
    int pop = bunpu[nowscore];
    string status= "pro";
    if( pop *100 >= 99*size ) status = "pro";
    else if( pop * 100>=90 * size ) status = "hardcore";
    else if( pop*100 >= 80*size) status = "average";
    else if( pop*100 >= 50*size) status = "random";
    else status = "noob";
    cout << nowplayer << " " <<status<< endl;
    it++;
  }
  return 0;
}

Problem C. Geometry Horse

問題

標的の個数・点数が入力として与えられる．
それとは別に配列が与えられ，
壊した標的の個数が以上ならば，一つの標的を壊したとき，その標的の点数にをかけたものが得点として得られる．
すべての標的を壊す時の得点最大値を答えよ

考えたこと

ただのgreedyです

コード

int main(){
  int n_figure;
  cin >> n_figure;
  vector< pair<int,int> > vec;
  for( int i = 0 ; i < n_figure ;i++ ){
    int k,c;
    cin >> k>>c;
    vec.push_back( make_pair( c,k ) );
  }
  sort( vec.begin(), vec.end() );
  int t;
  cin >> t;
  vector<long long> ps;
  for( int i = 0 ; i < t ; i++ ){
    ll p;
    cin >> p;
    ps.push_back( p );
  }
  long long n_des = 0;
  int ind_p = 0;
  long long ans = 0;
  for( int i = 0 ; i < vec.size(); i++ ){
    ll des = vec[i].second;
    int weight = vec[i].first;
    if( ind_p<(int)ps.size() && n_des+vec[i].second > ps[ind_p] ){
      des = ps[ind_p]-n_des;
      ans += weight*des*(ind_p+1);
      //cout << weight <<"*" << des <<"*" << (ind_p+1) << endl;
      vec[i].second -= des;
      ind_p++;
      i--;
    }
    else{
     // cout << weight <<"*" << des <<"*" << (ind_p+1) << endl;
      ans += ((ll)weight)*des*(ind_p+1);
    }
    n_des += des;
  }
  cout << ans << endl;

  return 0;
}