naoya_t@topcoder

Member SRM474

11:57 |

リハビリ

rankalee先生と同じ部屋

DIV	level	問題名	競技中	後で	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

• グラフとかdijkstraとか鬼門（概念的にもデバッグ的に）
• 間に合わず

Hard(1000): 開いてない

Challenge Phase

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

System Test

• 250x2,1000x2が落ちてた

結果

233.34points

Room: 9/20

Div1: 237/487

1489→1509黄

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