Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-05-25

TCO2010 Qualification Round 3

| 10:57 | TCO2010 Qualification Round 3 - naoya_t@topcoder を含むブックマーク はてなブックマーク - TCO2010 Qualification Round 3 - naoya_t@topcoder TCO2010 Qualification Round 3 - naoya_t@topcoder のブックマークコメント

  • みんなQR2までで通っちゃってるみたいで寂しいQR3
  • 難易度は普段のDiv2程度?妙に易しく感じられた
  • 3問全部submitできたのってDiv1・Div2通して初めてだ
  • 一瞬全体の20番台だった!コンテスト中なので通るかはまだ不明…お願い600以内に残って
  • →500が恥ずかしいミスで落ちて111位。とりあえず予選通過。そしてとりあえず黄色に戻れた

教訓:

配列は端をちゃんと見る

  • レーヴェンシュタイン距離5未満のミスで落ちた場合は何かペナルティを課すことにしよう…
DIVlevel問題名競技中後でSystem Test通過率備考levenshtein
- 250 SumRectangle 提出 - passed - 224.76 (9'44'') -
- 500 WhatThisChord 提出 - failed - 459.62 (8'33'')→0 4
- 1000 CuttingGlass 提出 - passed - 625.24 (25'27'') -

(※以下、コードは終了後に貼りつけました。念のため)

Easy(250): SumRectangle

  • 右下から見てて時間ロスした
  • 左上から見たら簡単だった
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

class SumRectangle {
 public:
  int getCorner(vector <int> leftColumn, vector <int> topRow) {
	int w=sz(topRow), h=sz(leftColumn);
    vector<vector<int> > sr(h,vector<int>(w,0));
    rep(x,w) sr[0][x] = topRow[x];
    rep(y,h) sr[y][0] = leftColumn[y];
    for(int y=1;y<h;y++){
      for(int x=1;x<w;x++){
        sr[y][x] = sr[y-1][x-1] - sr[y-1][x] - sr[y][x-1];
      }
    }
    return sr[h-1][w-1];
  }
};

Medium(500): WhatThisChord

  • 部屋で一番乗り
  • と思って喜んでいたが最後の"B"を書き忘れててFailed System Test。そこを直せば通ります。
  • 誰も撃墜してこなかった件
const char *name[12] = {"C","C#","D","D#","E","F","F#","G","G#","A","A#"}; /// OOPS
int bases[6] = {4,9,2,7,11,4};

class WhatsThisChord {
 public:
  string classify(vector <int> chord) {
    map<set<int>,pair<int,bool> > ans;
    rep(i,12){
      set<int> smaj,smin;
      smaj.insert(i); smin.insert(i);
      smaj.insert((i+4)%12); smin.insert((i+3)%12);
      smaj.insert((i+7)%12); smin.insert((i+7)%12);
      ans[smaj] = pair<int,bool>(i,true);
      ans[smin] = pair<int,bool>(i,false);
    }
    
    int b = 0; bool maj = true;
    set<int> ns;
    rep(i,6) if (chord[i]>=0) ns.insert((bases[i]+chord[i])%12);

    if (found(ans,ns)) {
      pair<int,bool> a = ans[ns];
      stringstream ss;
      ss << name[a.first];
      if (a.second) ss << " Major"; else ss << " Minor";
      return ss.str();
    } else {
      return "";
    }
  }
};

Hard(1000): CuttingGlass

  • 碁盤の目の各マスを頂点とし、隣りあったマス同士を結ぶ辺があるグラフ構造で、ダイヤモンドカッターが動いて辺を切っていく。
  • union-findするだけな気が
    • 昨日PKUの問題でunion findを使ったばかりなので記憶に新しい!!
class UF {
  vector<int> data;
 public:
  UF(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
};

class CuttingGlass {
  int sx,sy,n,w,h;
 public:
  int pieces(int W, int H, int startx, int starty, vector <string> program) {
	int pn=sz(program); string prog=""; rep(i,pn) prog += program[i];
    sx=startx; sy=starty; n=sz(prog); w=W; h=H;

    vector<int> mx(256,0), my(256,0);
    mx['U']=mx['D']=my['L']=my['R']=0;
    mx['R']=my['D']=1; mx['L']=my['U']=-1;

    vector<vector<int> > horiz(h+1,vector<int>(w,0));
    vector<vector<int> > vert(w+1,vector<int>(h,0));
    int x0=sx, y0=sy;
    rep(i,n){
      int x1=x0+mx[prog[i]], y1=y0+my[prog[i]];
      if (x0==x1) {
        int _y0=min(y0,y1);//, _y1=max(y0,y1);
        if (0<=_y0 && _y0<h) vert[x0][_y0] = 1;
      } else if (y0==y1) {
        int _x0=min(x0,x1);//, _x1=max(x0,x1);
        if (0<=_x0 && _x0<w) horiz[y0][_x0] = 1;
      }
      x0=x1; y0=y1;
    }
    UF uf(H*W);
    rep(r,H) rep(c,W){
      int me=c+r*W;
      if(r>=1){
        int ue=c+(r-1)*W;
        if (!horiz[r][c]) uf.unionSet(me,ue);
      }
      if(c>=1){
        int hd=(c-1)+r*W;
        if (!vert[c][r]) uf.unionSet(me,hd);
      }
    }
    set<int> aaa;
    rep(i,H*W){
      aaa.insert(uf.root(i));
    }
    return sz(aaa);
  }
};

Challenge Phase:

/// Challenge前:1309.62point, room3/24, total36/1097

/// Challenge後:1309.62point, room2/24, total39/1097

  • 割と人のやつ読んだけど落とすのなかった。自分も落とされず。
  • 赤の人に黙って1000点問題を閉じられた時の安心感に名前をつけたい

System Test

oxo ...500落ちた。ソース見返す。

const char *name[12] = {"C","C#","D","D#","E","F","F#","G","G#","A","A#"};

って何だw

折角500点問題一番乗りできたと思ったがやはり詰めが甘かった。

夢の三完は成らず。850点。

Room: 5/24

全体: 111/1097 ...500点が通ってれば29位だった。次(本選!)がんばる。

1453→1528 黄復帰

http://gyazo.com/49bfa1fefaa02c9e87b8d8e9d88d0757.png

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