arc076.contest.atcoder.jp
1完300点で463位
ARCに出たのってもしかして初めてだったか
いやそんなことなかった…少なくとも2012年5月のARC002に出てる
Standings - AtCoder Regular Contest 002 | AtCoder
リジャッジ対象者リストにも名前があったw
当時とはレーティングの仕組みも変わってるのか
(レーティング258って… 下から上がっていくのを楽しむシステムか)
C. Reconciled?
・それぞれのpermutationをmodを取りながらの階乗で求めて
・どう入れ違いにするか(同数なら前後の2パターン、1つ違いなら挟み込む1パターン)
というだけの話
AC
// 略 #define M 1000000007LL ll f(int k) { ll x = 1LL; for (int i=2; i<=k; ++i) { x = (x * i) % M; } return x; } int main(){ int n,m; cin >> n>>m; if (abs(n-m) > 1) { cout<<0<<endl; return 0; } ll nf = f(n), mf = f(m), al = nf * mf % M; if (n==m) al = al*2 % M; cout << al << endl; return 0; }
D. Built?
最小全域木を作りたいんだけど
x軸, y軸それぞれに投影したやつをソートして
いや全都市相互間の距離を求めるだけの時間はないから
計算量減らさなくちゃ
既に繋いだ都市集合と、繋いでない都市集合があるとして
新たに繋いだ都市から、繋いでない都市で一番近いやつをx軸y軸でそれぞれ2つ拾って、とかやってたけど
(前後左右の近傍)
(ソート済み配列を二分探索して挿入したり削除したりしてた…これはsetとかmapでやるべきか;削除を考えなくても、priority_queue作って、使用済みをスキップする感じで十分だったか)
実装でうまく行ってなかった
コンテスト後
setとかmapとか、multimapとか色々試してたけど、
答えは合うんだけど半分ぐらいのケースでTLE。沢山の都市が近接してるケースなどで死ぬっぽい。
公式解説を読んだ。
そうか、(投影したx軸ないしy軸の上で)隣りの隣りの都市に繋ぐのは、隣りに繋いでそこからさらに隣りに繋ぐのと等価だから、跨いだようなpathをわざわざ引かなくても良くて、隣接する左右(上下)1つずつとのpathだけ使えばいいのね;(そこが腑に落ちてなくて、というか反例があるんじゃないかと思っていて、近傍都市をどこまで探索する必要があるのか、という所でずっと悩んでいた)
だとしたら、 をソートしたやつを作ったときに隣り合った都市どうしの間のpathから、1つずつ調べるとかじゃなくて全部priority_queueに突っ込んで、(yも同様に同じpriority_queueに突っ込んで)、短い順に、違う島に属する2都市を繋ぐやつかをunion-findで見ながらばんばん繋いでいくだけだ。(クラスカル法)
それなら簡単。(ごりごり書いてたコードの1/3ぐらいの長さに収まったw)
→AC
// いろいろ略 ll solve(int n, vector<int>&x, vector<int>&y) { assert(x.size() == n && y.size() == n); vector<ii> xx(n), yy(n); rep(i, n) { xx[i] = ii(x[i], i); yy[i] = ii(y[i], i); } sort(ALL(xx)); sort(ALL(yy)); UnionFind uf(n); priority_queue<pair<int,ii>> pq; rep(i, n-1) { pq.push(make_pair(-(xx[i+1].first - xx[i].first), ii(xx[i].second, xx[i+1].second))); pq.push(make_pair(-(yy[i+1].first - yy[i].first), ii(yy[i].second, yy[i+1].second))); } ll cost = 0; while (!pq.empty()) { int d = -pq.top().first; int u = pq.top().second.first, v = pq.top().second.second; pq.pop(); if (uf.root(u) == uf.root(v)) continue; cost += d; uf.unionSet(u, v); if (uf.size(u) == n) break; } return cost; } int main(){ int N = loadint(); vector<int> tmp(2); vector<int> x(N), y(N); rep(i, N) { loadvec(tmp, 2); x[i]=tmp[0]; y[i]=tmp[1]; } printf("%lld\n", solve(N, x, y)); return 0; }
E. Connected?
開いてない
F. Exhausted?
開いてない