Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-05-03

TCO10 Qualification Round 1 (再試合)

09:37 | TCO10 Qualification Round 1 (再試合) - naoya_t@topcoder を含むブックマーク はてなブックマーク - TCO10 Qualification Round 1 (再試合) - naoya_t@topcoder TCO10 Qualification Round 1 (再試合) - naoya_t@topcoder のブックマークコメント

DIVlevel問題名競技中後でSystem Test通過率備考
- 250 GirlsAndBoys 提出 - passed - 206.39
- 500 RobotSimulation 提出 - failed - 0
- 1000 SequenceMerger 間に合わず -

Easy(250): GirlsAndBoys

  • 最後に GGGGGGG...BBBBB か BBBBBBB...GGGGG になる
  • その2パターンとの編集距離の小さい方か
  • と思ったけど違った。答えあわない
  • あ。隣り同士しか交換できない。問題よく読め
  • だったら
    • Σ(現在の各Gの位置)-Σ(Gが左に集まった場合)
    • Σ(現在の各Bの位置)-Σ(Bが左に集まった場合)
  • の小さい方で良くね?
  • 書き直し
  • サンプルケース全部通る
  • 境界条件みる。行けそ
  • 提出
  • なにもうみんな先に解いてた…問題読み違えてた分のロスか
...
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()

class GirlsAndBoys {
 public:
  int sortThem(string row) {
    int n=sz(row); if(n==1) return 0;
    int gc=0,bc=0,gn=0,bn=0,gt=0,bt=0;
    rep(i,n) {
      if(row[i]=='G'){
        gn++;gc+=i;
      }else{
        bn++;bc+=i;
      }
    }
    gt=gn*(gn-1)/2;
    bt=bn*(bn-1)/2;
    return min(gc-gt,bc-bt);
  }
};

Medium(500): RobotSimulation

  • 同じパターンの繰り返しなら、n回目と(n+1)回目の差分は一定になるはず
  • 最初の2,3回で届きそうなエリアの分の二次元配列を持っといて、訪問された点がいくつか数えるのは大した計算量ではなさそう
  • 1回目 + (2回目-1回目)*(times-1) ?
  • いや違う。サンプル通らない
  • ああ。もうちょっとやんないと駄目か
  • 10回ぐらい?
  • それでサンプルケース通るっぽい
  • 心配なのでもうちょい
  • 12回にしてみる
  • 提出
...
#define sz(a)  int((a).size())
#define pb  push_back
#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())

#define R 120
#define W (R+R+1)

class RobotSimulation {
  int x, y;
  bool visited[W][W];
  void run(const string& program){
    tr(program,it){
      switch(*it){
        case 'U': y--; break;
        case 'D': y++; break;
        case 'R': x++; break;
        case 'L': x--; break;
      }
      visited[x][y] = true;
    }
  }
  int count(){
    int c=0;
    rep(i,W)rep(j,W) if(visited[i][j])c++;
    return c;
  }
 public:
  int cellsVisited(string program, int times) {
    rep(i,W)rep(j,W) visited[i][j]=false;

    x=y=R; visited[x][y]=true;
    vector<int> cz(11,0); ///OOPS
    rep(i,12){
      cz[i] = count();
      if (times == i) return cz[i];
      run(program);
    }
    return cz[11]+(cz[11]-cz[10])*(times-11);
  }
};

Hard(1000): SequenceMerger

  • 等差数列(A)、等比数列(G)、その他(E)
  • 入力をパースして
  • とりあえず1e9以内に収まるように書き換えて
  • さてどうする
  • 1〜1e9で二分探索させて、positions[i]番目の内輪で最大っぽいところを探して合計すれば行ける?
  • 近いとこまで行けるけど、合わないのがある
  • あーもう時間ない

Challenge Phase:

  • 落とさず、落とされず

System Test

  • (o x -)
  • なにー
  • あー。添字0から11まで使ってるのにvector<int>(11,0)とか何それ。最後に12に増やしたのが仇になった
  • Practice roomで12に直してsubmitしたら通った
  • そんなの書いてるようじゃあいずれにせよ駄目だな
  • 誰かに撃墜されてもよさそうなポイントだけど...
  • でもなんでローカルで通るのそれ

Room: 21/24

全体: 676/956

参加者1000人切ってたのに予選通過ライン600に入れないって何それ ... レーティングも1298まで落ちた。TCOで悪い点とるとレーティング落ちまくるので怖い。

http://gyazo.com/1c554a69036b6bc2cf067fcaa75126dd.png

5/12にまた出る。

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