AtCoder Regular Contest 076

arc076.contest.atcoder.jp
1完300点で463位
ARCに出たのってもしかして初めてだったか

いやそんなことなかった…少なくとも2012年5月のARC002に出てる
Standings - AtCoder Regular Contest 002 | AtCoder
リジャッジ対象者リストにも名前があったｗ
当時とはレーティングの仕組みも変わってるのか
（レーティング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ぐらいの長さに収まったｗ）
→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?

開いてない