Hatena::Grouptopcoder

IH19980412の日記

 | 

2013-04-27

SRM577

19:04

久々のSRM。青に別れを告げに行く。

Easy:

・期待値?

・普通にやればいいよね

・(バグとの死闘)

・やっとサンプル通った...

・submit

#include <cstdio> 
#include <cstring> 
#include <cstdlib> 
#include <cmath> 
#include <string> 
#include <algorithm> 
#include <vector> 
#include <queue> 
#include <stack> 
#include <functional> 
#include <iostream> 
#include <map> 
#include <set> 
using namespace std; 
typedef pair<int,int> P; 
typedef pair<int,P> P1; 
typedef pair<P,P> P2; 
#define pu push 
#define pb push_back 
#define mp make_pair 
#define eps 1e-7 
#define INF 2000000000 
class EllysRoomAssignmentsDiv1{ 
public: 
double getAverage(vector <string> ratings){ 
vector<int>rate; 
int own; 
string go=""; 
  for(int i=0;i<ratings.size();i++) 
  { 
    go+=ratings[i]; 
  } 
  for(int i=0;i<go.size();i+=5) 
  { 
    int a=go[i]-'0'; 
    int b=go[1+i]-'0'; 
    int c=go[i+2]-'0'; 
    int d=go[i+3]-'0'; 
    rate.pb(a*1000+b*100+c*10+d); 
    if(!i) own=a*1000+b*100+c*10+d; 
  } 
  sort(rate.begin(),rate.end(),greater<int>()); 
  int room=rate.size(); 
  room=(room+19)/20; 
  if(room==1) 
  { 
    double sum=0.0; 
    for(int i=0;i<rate.size();i++) sum+=(double)rate[i]; 
    sum/=(double)rate.size(); 
    return sum; 
  } 
  double ret=0.0; 
  double beh; 
  bool out=false; 
  int div=0; 
  bool kak=0; 
  for(int i=0;;i++) 
  { 
    double res=0.0; 
    for(int j=i*room;j<min((int)rate.size(),(i+1)*room);j++) 
    { 
      res+=(double)rate[j]; 
      if(j==rate.size()-1) out=true; 
    } 
    res/=(double)(min((int)rate.size(),(i+1)*room)-i*room); 
    if(rate[i*room]>=own && own>=rate[min((int)rate.size(),(i+1)*room)-1]){ 
      res=(double)own; 
      if(out) kak=1; 
    } 
    if(out) beh=ret; 
    ret+=res; 
    div++; 
    if(out) break; 
  } 
  double ans; 
  if(!kak){ 
    ans=ret/(double)(div)*((double)(rate.size()%room==0?room:rate.size()%room)/(double)(room)); 
    ans+=beh/(double)(div-1)*((double)((room-rate.size()%room)==room?0:(room-rate.size()%room))/(double)(room)); 
  }else{ 
    ans=ret/(double)div; 
  } 
  return ans; 
  } 
};

Medium:

・貪欲?

・しらん

終わり

systest 通る

o-- +0/-0 355位

rating 1381->1436(+55) Highest

黄色にはなれなかったけど王手をかけたのでよしとする

あとマンハッタン距離の問題は45°回しましょう(戒め)

 |