nodchipのTopCoder日記

■ Codeforces Round #134 (Div. 1) 19:02

急にVisual Studio 2012 RCでデバッグ実行ができなくなって焦りました。

A. Ice Skating

• Snow driftsの単語の意味がわからないけど、きっとそこに行けば停止できるようなマスなのだと思う
• 初期状態で行き来ができる集合同士は1箇所Snow driftを設置すれば互いに行き来できるようになるはず
• ならば集合の数-1が答え

int main() {
	std::ios::sync_with_stdio(false);

  int N;
  cin >> N;
  UnionFind uf(N);
  vector<pair<int, int> > snowDrifts;
  REP(n, N) {
    int x, y;
    cin >> x >> y;
    REP(i, n) {
      if (snowDrifts[i].first == x || snowDrifts[i].second == y) {
        uf.unionSet(i, n);
      }
    }
    snowDrifts.push_back(MP(x, y));
  }

  set<int> roots;
  REP(n, N) {
    roots.insert(uf.root(n));
  }

  cout << roots.size() - 1 << endl;
}

B. Blackboard Fibonacci

• 枝刈り探索で行けたりする・・・？
• 書いてみる
• サンプル通った
• 出してみる
• Time limit exceeded on pretest 7
• どんなケースでTLEしてるんだろう・・・？
• ランダム入力を突っ込んでみる
• 58 790080 で止まった・・・
• むりぽ

C. Formurosa

読んでいません

D. Bitonix' Patrol

読んでいません

E. Alien DNA

読んでいません

System Test

#	Who	=	*	A 500	B 1000	C 2500	D 3000	E 3000
119	nodchip	492	0	+ 00:04-1

1989->1982 Aのおかげで命拾いしました。

ツイートする