naoya_t@topcoder

TCO2010 Qualification Round 3

TCO2010 | 10:57 |

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

教訓：

配列は端をちゃんと見る

• レーヴェンシュタイン距離5未満のミスで落ちた場合は何かペナルティを課すことにしよう…

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

って何だｗ

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

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

Room: 5/24

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

1453→1528 黄復帰