naoya_t@topcoder

TCO10 Qualification Round 1 (再試合)

09:37 |

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

Easy(250): GirlsAndBoys

• 最後に GGGGGGG...BBBBB か BBBBBBB...GGGGG になる
• その２パターンとの編集距離の小さい方か
• と思ったけど違った。答えあわない
• あ。隣り同士しか交換できない。問題よく読め
• だったら
  • Σ（現在の各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で悪い点とるとレーティング落ちまくるので怖い。

5/12にまた出る。