Hatena::Grouptopcoder

shnyaの参戦記録

2011-05-23練習

省エネモードで。

SRM 171 Div1 Easy 02:28  [http://www.topcoder.com/stat?c=problem_statement&pm=1950&rd=4660:title=SRM 171 Div1 Easy] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=1950&rd=4660:title=SRM 171 Div1 Easy] - shnyaの参戦記録

合計数えてpair使ってsortするだけ。

6位の扱いとか問題の読み違えではまる。

#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

class CrossCountry {
public:
  string scoreMeet( int numTeams, string finish ) {
    string s = finish;
    sort(s.begin(),s.end());
    s.erase(unique(s.begin(),s.end()),s.end());
    vector<pair<pair<int,int>,char> > v;
    REP(i,SZ(s)){
      int score = 0, count = 0, sixth = numeric_limits<int>::max();
      REP(j,SZ(finish)){
        if(finish[j] == s[i]){
          if(count == 5){
            sixth = j + 1;
            break;
          }
          score += j + 1;
          count++;
        }
      }
      if(count >= 5){
        v.push_back(make_pair(make_pair(score,sixth),s[i]));
      }
    }
    sort(v.begin(),v.end());
    //debug(v);
    string res = "";
    REP(i,numTeams){
      if(i == SZ(v)) break;
      res += v[i].second;
    }
    return res;
  }
};

SRM 171 Div1 Medium 02:28  [http://www.topcoder.com/stat?c=problem_statement&pm=1941&rd=4660:title=SRM 171 Div1 Medium] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=1941&rd=4660:title=SRM 171 Div1 Medium] - shnyaの参戦記録

全探索の問題。

近い問題をEulerでやったけど、与えられた抵抗を全て使う必要がないという点を読み違えてた。

#define SZ(a) int((a).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

class ResistorCombinations {

  static long double tod(const string &str){
    long double res;
    istringstream iss(str);
    iss >> res;
    return res;
  }

public:
  double closestValue(vector <string> resist, double target ) {
    vector<long double> _v(resist.size());
    transform(resist.begin(),resist.end(),_v.begin(),tod);
    long double res = 0, mind = numeric_limits<long double>::max();
    queue<vector<long double> > Q;
    Q.push(_v);
    while(!Q.empty()){
      vector<long double> v2 = Q.front();
      Q.pop();
      REP(i,SZ(v2)){
        if(abs(v2[i] - target) < mind){
          res = v2[i];
          mind = abs(v2[i] - target);
        }
      }
      if(v2.size() == 1) continue;
      for(int i = 0; i < SZ(v2); i++){
        for(int j = i + 1; j < SZ(v2); j++){
          vector<long double> v = v2;
          long double a = v[i], b = v[j];
          swap(v[j],v.back());
          v.pop_back();
          swap(v[i],v.back());
          v.pop_back();
          v.push_back(a + b);
          Q.push(v);
          v.pop_back();
          v.push_back(a * b / (a + b));
          Q.push(v);
          v.pop_back();
        }
      }
    }
    return res;
  }
};

SRM 473 Div1 Easy 02:28  [http://www.topcoder.com/stat?c=problem_statement&pm=10979&rd=14155:title=SRM 473 Div1 Easy] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10979&rd=14155:title=SRM 473 Div1 Easy] - shnyaの参戦記録

周期性があるかどうかをシミュレートする問題。

サンプルが親切。

適当な回数回して、原点に戻ったら周期性ありと判断。

シミュレート部分はやるだけ。

#define SZ(a) int((a).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

int dir[4][2] = {
  {1,0}, {0,-1},{-1,0},{0,1}
};

class SequenceOfCommands {
public:
  string whatHappens(vector<string> com) {
    string str = accumulate(com.begin(),com.end(),string(""));
    int d = 0;
    int x = 0, y = 0;
    for(int i = 0; i < 100; i++){
      REP(i,SZ(str)){
        if(str[i] == 'S'){
          x += dir[d][0];
          y += dir[d][1];
        }else if(str[i] == 'R'){
          d++;
          if(d == 4) d = 0;
        }else{
          d--;
          if(d == -1) d = 3;
        }
      }
      if(x == 0 && y == 0){
        return "bounded";
      }
    }
    return "unbounded";
  }
};

SRM 473 Div1 Medium 02:28  [http://www.topcoder.com/stat?c=problem_statement&pm=10976&rd=14155:title=SRM 473 Div1 Medium] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10976&rd=14155:title=SRM 473 Div1 Medium] - shnyaの参戦記録

円に内接する直角三角形の個数を求める。

上手にやらないとTLEする。

あとsetの場合、lower_boundはsetのメンバ関数を使った方がかなり早い。当然のことだがこれから気をつける。

)
  set<int> s;
  set<int>::iterator itr;
  itr = s.lower_bound(target);
  itr = lower_bound(s.begin(),s.end(),target);
#define SZ(a) int((a).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())

class RightTriangle {
public:
  long long triangleCount( int places, int points, int a, int b, int c ) {
    if(places % 2 == 1) return 0;
    vector<LLI> v;
    {
      set<int> v2;
      REP(i,places) v2.insert(i);
      LLI _a = a, _b = b, _c = c;
      for(LLI i = 0; i < points; i++){
        int res = (_a * i * i  + _b * i + _c) % places;
        set<int>::iterator itr = v2.lower_bound(res);
        if(itr == v2.end()){
          itr = v2.lower_bound(0);
        }
        v.push_back(*itr);
        v2.erase(itr);
      }
    }
    SORT(v);
    LLI res = 0;
    for(int i = 0; i < SZ(v); i++){
      if(v[i] >= places / 2) break;
      if(binary_search(v.begin(),v.end(),v[i]+(places/2))){
        res += points - 2;
      }
    }
    return res;
  }
};