Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-07-01

Member SRM474

11:57 | Member SRM474 - naoya_t@topcoder を含むブックマーク はてなブックマーク - Member SRM474 - naoya_t@topcoder Member SRM474 - naoya_t@topcoder のブックマークコメント

リハビリ

rankalee先生と同じ部屋

DIVlevel問題名競技中後でSystem Test通過率備考levenshtein
1 250 RouteIntersection o - passed (233.34) - _ 0
1 500 TreesCount 開いた - - - _ ?
1 1000 - 開いてない - - - _ ?

Easy(250): RouteIntersection

  • 最大10e9次元(のうち高々50次元)空間
  • sparseなのでmap使うか
  • passed; 233.34
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

class RouteIntersection {
 public:
  string isValid(int N, vector <int> coords, string moves) {
    bool ans = true;
    int n=sz(coords);//1-50
    map<int,int> cd;
    set<map<int,int> > vd;
    rep(i,n){
      cd[ coords[i] ]=0;
    }
    vd.insert(cd);
    rep(i,n){
      int x=coords[i];
      int inc=(moves[i] == '+')? 1 : -1;
      cd[x] += inc;
      if (found(vd,cd)) { ans=false; break; }
      vd.insert(cd);
    }
    return ans ? "VALID" : "NOT VALID";
  }
};

Medium(500): TreesCount

Hard(1000): 開いてない

Challenge Phase

  • 落とさず落とされず
  • 赤の人が500を2つ落とした

System Test

  • 250x2,1000x2が落ちてた

結果

233.34points

Room: 9/20

Div1: 237/487

1489→1509黄

もう黄色になったぐらいじゃ嬉しくなんかないんだからね

http://gyazo.com/6e6659fc3f01933e6a70a43a896e0996.png

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100701