Codeforces#24

SRMが無くてつまんないので、TLでちょくちょく見かけてたCodeforcesに参加してみた。
A,B,Cを解いて182位/レーティング1549。やったね！TopCoderよりずっと高いよ！

A - Ring Road

一方通行の道で円環状に繋がった都市群がある。都市番号は順不同。それぞれの道は固有のコストを払うことで一方通行の向きを反転できる。なるべく少ないコストで、どの都市からでも一周できるように道を繋げ、という問題。
最初円環状という条件を見落としてて、なにこれAから重すぎだろ・・・とか思った。とりあえず都市番号が順不同、道の順番も順不同というのでハマってデータ構造の決定にかなり時間がかかって、30分くらい考えてた。
最終的なアルゴリズムは、どこかの都市から道を適当な向きにたどって行って、進行方向と違う向きの道が出たら反転させるためのコストを追加して次の都市へ行く、というのを一周分繰り返すのになった。あとは全部の道のコスト合計を覚えておけば、逆回りするときのコストは引き算一発で出る。

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

struct Road {
    int from, to, c;
};

int main() {
    int N;
    cin >> N;

    vector<Road> roads;
    int all_cost = 0;
    for(int i = 0; i < N; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        Road r;
        r.from = a;
        r.to = b;
        r.c = c;
        roads.push_back(r);
        all_cost += c;
    }

    int curr = 1;
    int cost = 0;
    vector<bool> used(N, false);
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            if(used[j]) continue;
            if(roads[j].from == curr || roads[j].to == curr) {
                int next = roads[j].from == curr ? roads[j].to : roads[j].from;
                if(roads[j].to == curr) cost += roads[j].c;
                curr = next;
                used[j] = true;
                break;
            }
        }
    }

    cout << min(cost, all_cost-cost) << endl;
    return 0;
}

B - F1 Champions

F1グランプリの順位が与えられるから、似てるけど異なる二つの順位付け方法でそれぞれ優勝者を決めろ、という問題。
一つは

• 順位点の合計が大きい人が優勝
• 同点がいるなら、1位になった回数の多いほうが優勝
• 以下、2位、3位・・・の回数を比較

もう一つは

• 1位になった回数の多いほうが優勝
• 同着がいるなら、順位点の合計が大きい人が優勝
• 以下、2位、3位・・・の回数を比較

やるだけだけど、二つめの時の順位点のmaxを一つめと同じものにしてしまっていて1WA。
ソースは非常に汚いので割愛・・・。

C - Sequence of Points

点MとA₀からA_n-1が与えられて、MをA_iに対して点対称な位置に移動させることを、i=0,1,・・・n-1,0,1・・・に対してj回繰り返したとき、点がどこに来るかを答える問題。
条件は二つ。nは奇数。jは最大10¹⁸とかあるので、シミュレーションすると死ぬ。
シミュレーションできないので、とりあえず行列で書いてみる。x座標の変換は、

だから、A₀からA_n-1まで全部掛けると変換行列は

ここで、nは奇数だから(0,0)要素は常に-1。ということは、この行列は2乗すると単位行列になる！
ということで、まずはj div nの偶奇で行列の状態を求め、それからj mod n点ぶんをシミュレーションすれば良い。
・・・最初は(0,0)が常に1だと勘違いしてWA。次はこれを桁溢れで死んだと思って、Rubyで書き直してやっぱりWA。合計2WA。
答えは少なくともlong longで余裕で入るぽいです。
ソース。やってるときはここまでちゃんと考えてなかったので少し汚い。

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

typedef long long LL;
typedef pair<int, int> Point;

int main() {
    LL n, j;
    cin >> n >> j;

    Point init;
    vector<Point> as;

    cin >> init.first >> init.second;
    LL sum_x = 0, sum_y = 0;
    for(int i = 0; i < n; ++i) {
        sum_x *= -1;
        sum_y *= -1;

        int x, y;
        cin >> x >> y;
        sum_x += 2*x;
        sum_y += 2*y;
        as.push_back(make_pair(x, y));
    }

    LL loopcnt = j / n;
    LL mod = j % n;
    LL coef_x = sum_x*(loopcnt&1), coef_y = sum_y*(loopcnt&1);
    for(int i = 0; i < mod; ++i) {
        coef_x *= -1;
        coef_y *= -1;
        coef_x += 2*as[i].first;
        coef_y += 2*as[i].second;
    }

    LL flg = (j&1) ? -1 : 1;
    cout << init.first*flg + coef_x << ' ' << init.second*flg + coef_y << endl;
    return 0;
}

D,E

解いてない。
Dは確率だから分かればすぐなんだろうなー、と思いつつ、5分で解くのは流石に無理ゲー。あとでやってみよう。