Hatena::Grouptopcoder

れんしゅうちょう。 このページをアンテナに追加 RSSフィード

2015-06-26ICPC2015 国内予選 G (参加記でゎない)

notさんのを見習って僕も書いてみた.

方針は zerokugiさんのと同じ.

線分をむりやり符号付きにしてやると楽なようだ.

サンプルは通った.

ライブラリ除いて50行くらい.

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); ++i)

#define X real()
#define Y imag()
using R = long double;
using P = complex<R>;
using L = pair<P, P>;
const R EPS = 1E-8;
#define fst first
#define snd second
inline int sgn(const R &r){ return (r > EPS) - (r < -EPS); }
inline int sgn(const R &a, const R &b){ return sgn(a-b); }
namespace std{
    bool operator<(const P &a, const P &b){
        return sgn(a.X, b.X) ? a.X < b.X : sgn(a.Y, b.Y) < 0;
    }
}
inline R dot(const P &a, const P &b){ return real(conj(a) * b); }
inline R det(const P &a, const P &b){ return imag(conj(a) * b); }
inline P vec(const L &l){ return l.snd - l.fst; }
enum CCW{FRONT = 1, RIGHT = 2, BACK = 4, LEFT = 8, ON = 16, };
inline int ccw(const L &l, const P &p){
    P b = p - l.fst, c = l.snd - l.fst;
    if(int scr = sgn(det(c, b))) return scr < 0 ? RIGHT : LEFT;
    if(sgn(dot(c, b)) < 0) return BACK;
    return sgn(norm(c), norm(b)) < 0 ? FRONT : ON;
}
inline vector<P> pLL(const L &l, const L &m){
    if(sgn(det(vec(l), vec(m))) == 0) return vector<P>(0);
    R A = det(vec(m), vec(l));
    R B = det(vec(m), m.snd - l.fst);
    return vector<P>(1, l.fst + B / A * vec(l));
}
inline P refLP(const L &l, const P &p){
    return (R)(2) * (l.fst + dot(p - l.fst, vec(l)) / norm(vec(l)) * vec(l)) - p;
}
vector<P> cut(const vector<P> &pol, const L &l){
    vector<P> res;
    rep(i, pol.size()-1){
        P a = pol[i], b = pol[i+1];
        L s(a, b);
        if(ccw(l, a) != RIGHT) res.emplace_back(a);
        if(sgn(det(vec(l), s.fst-l.fst)) * sgn(det(vec(l), s.snd-l.fst)) < 0)
            res.emplace_back(pLL(l, s).front());
    }
    res.emplace_back(res.front());
    return res;
}

bool solve(){
    int n; cin >> n;
    if(!n) return false;
    vector<P> in(n);
    for(auto &p : in){ R x, y; cin >> x >> y; p.real(x); p.imag(y); }
    in.emplace_back(in.front());
    pair<int, R> res(-1, 0);
    rep(i, n) rep(j, i){
        L l((in[i] + in[j]) / (R)(2), P(0, 0));
        l.snd = l.fst + P(0, 1) * (in[i] - in[j]);

        vector<P> a = cut(in, l); swap(l.fst, l.snd);
        vector<P> b = cut(in, l);
        for(auto &p : b) p = refLP(l, p);
        reverse(begin(b), end(b));

        vector<P> c = b;
        rep(i, a.size()-1) c = cut(c, L(a[i], a[i+1]));

        vector<P> ps;
        for(auto &p : a) ps.emplace_back(p);
        for(auto &p : b) ps.emplace_back(p);
        for(auto &p : c) ps.emplace_back(p);
        auto near = [](const P &a, const P &b){ return sgn(abs(a-b)) == 0; };
        sort(begin(ps), end(ps));
        ps.erase(unique(begin(ps), end(ps), near), end(ps));

        vector<pair<L, int>> ls;
        rep(i, a.size()-1) ls.emplace_back(L(a[i], a[i+1]), +1);
        rep(i, b.size()-1) ls.emplace_back(L(b[i], b[i+1]), +1);
        rep(i, c.size()-1) ls.emplace_back(L(c[i], c[i+1]), -1);

        R len = 0;
        for(auto &ld : ls) len += ld.snd * abs(ld.fst.snd - ld.fst.fst);

        map<pair<int, int>, int> es;
        for(auto &ld : ls){
            vector<pair<P, int>> qs;
            rep(i, ps.size()) if(ccw(ld.fst, ps[i]) == ON) qs.emplace_back(ps[i], i);
            sort(begin(qs), end(qs));
            rep(i, qs.size()-1) es[make_pair(qs[i].snd, qs[i+1].snd)] += ld.snd;
            rep(i, qs.size()-1) es[make_pair(qs[i+1].snd, qs[i].snd)] += ld.snd;
        }
        int cnt = 0;
        vector<vector<P>> g(ps.size());
        for(auto &e : es) if(e.snd) g[e.fst.fst].emplace_back(ps[e.fst.snd]);
        for(auto &v : g) assert(v.size() == 0 or v.size() == 2);
        rep(i, g.size()) if(g[i].size() == 2) cnt += ccw(L(g[i][0], g[i][1]), ps[i]) != ON;
        res = max(res, make_pair(cnt, len));
    }
    printf("%.6Lf\n", res.snd);
    return true;
}

int main(void){
    while(solve());
}

2015-03-14RUPC2015 day1

[]RUPC2015 day1 00:17

問題

odan さんと omurice さんと出ていました.

僕はコーディングをしていなかったので, 懇親会を抜けだした後 indeed なうを解いた後書いて見ました.

とりあえずコードだけ.

続きを読む

2014-10-21ICPC2014 アジア地区予選 東京大会 ソース置き場

後から, A-H までを解きなおしてみました.

本番で書いたコードではありません.


続きを読む

2014-10-20ICPC2014 アジア地区予選 東京大会 参加記

[]ICPC2014 アジア地区予選 東京大会 参加記 23:18

去年に引き続き, チーム Sophinyan として, ACM/ICPC アジア地区予選 東京大会に参加しました.

結果は, 7完最下位の, 9 位(チーム順位) でした. 順位表

チーム順位大学順位国内チーム順位国内大学順位解いた問題数時間
98657/111089

酷いバグに苦しんで, 時間さえあれば解ける問題に時間を残せなかったなど, 反省点はありますが, 健闘できたかなぁと思います.

僕は, 選手としての ICPC はこれで終わりです.

運営/手伝いをして下さった方々, スポンサーの方々, JAG の皆様, 応援して下さった皆様, それから(同じチーム, またはライバルとして)一緒に闘って下さった皆様, ありがとうございました.


以下, 詳細.

提出時刻付きの順位表とかが後悔されたら, 時刻を挿入する更新をする可能性があります.

みなさん, 来年は, Twitter ID とアイコンが書いてある名札を下げてきましょう!!!!

*1

続きを読む

*1:超重要な一言を忘れていたので 2014/10/21 00:19 追記

2014-09-16JAG 夏合宿 参加記

[]JAG 夏合宿 2014 参加記 01:29

2日目の途中から参加した.

結果は,

2日目: 一人で参加. AとD の2完で20位.

3日目: @tokoharu_sakura さん, @mikecat_mixc さんと bugnyan で参加. A-D, F-H, K の 8完で6位.

4日目: @nsd_fb さん, @yuusti さんと Tera^nyan で参加. A-F の 6完で6位

でした. 楽しかったです. (小並感)

全体を通して, ワンチャンある問題が解けないという事が多かったように思う.

ワンチャンあると感じた問題が多いという事は, 強くなるチャンスであると信じて, 精進したいです.

あと, チーム戦楽しい. またいろんな人と組んでチーム戦してみたい.

チーム組んでくれた方々, JAGの方々, 某社の方々など, 色々ありがとうございました.

続きを読む

2014-07-12ICPC2014 国内予選 参加記

[]ICPC2014 国内予選 参加記 22:52

後輩2人と, チーム Sophinyan として, ACM/ICPC 国内予選に参加しました.

6完/7問で, 7位(チーム順位). 順位表

チーム順位大学順位解いた問題数時間
766/726280

2つ目の出力ファイルのタイムスタンプは次の通り.

ABCDEFG
6'5717'2058'22(1WA)82'36104'58-147'06

なんかこんないい順位になってしまっていいんだっけという感じだった.

アジア地区予選も頑張りたい.


以下, 時系列順の詳細.

見難くてごめんなさい.

僕の記憶容量3バイトくらいしかないので, 問題聞いたタイミングとか違うかも.


続きを読む

2014-03-20最大流問題について その3

前々回, 前回 に引き続き, 最大流問題についてです.

Dinic 法でのボトルネックは, 各ステップで, dfs によりブロッキングフローを求める部分でした.

前回は, O(nm) だったこの部分を O(n^2) に落としたアルゴリズムを二つ紹介しました.

今回は, ここを O(m \log n), 従って, 全体では O(mn \log n) にするアルゴリズムを紹介します.


続きを読む

2014-03-19最大流問題について その2

前回 に引き続き, 最大流問題についてです.

Dinic 法でのボトルネックは, 各ステップで, dfs によりブロッキングフローを求める部分でした.

Dinic 法では O(nm) だったこの部分を O(n^2) に落としたアルゴリズムを二つ紹介します.


続きを読む

2014-03-11最大流問題について.

いんとろ 02:05

最大流問題を解くアルゴリズムについて, ちょろっと書いておきます.

要約すると, 言いたいことは

  • Dinic のライブラリ持ってたら, 間違っていないかチェックしましょう. (注意1のやつ)
  • Dinic ちょっぱやな気がするけど, ワーストケースは遅いよ. (当然)

の二つです. 半分自分用のメモみたいなもんです.

Dinic についてちゃんと知っている人が読むメリットは多分無いです.

ツッコミなどあれば, ぜひお願いします.

蟻本のページ番号が書いてある時は, 第二版のものです.

最大流問題を知らない人は, 蟻本(p. 188から少し)を読んで下さい.

今回は, グラフ G=(V, E) 上で, S から T への最大流を求めたいとします.

また, n = |V|, m = |E| とします. (こんな準備要るのかな)


Dinic 法と, その注意点 02:05

最大流を解くアルゴリズムの一つに, Dinic 法というヤツがあります.

Dinic 法については, とりあえず, 蟻本のコラム(p. 194)に書いてある事を把握しましょう.

ここでは, "1ステップ" というのは, 一度 bfs をしてから, もう一度 bfs をするまでを指す事にします.

続きを読む

Dinic 法の速さ 02:05

Dinic 法は, 上で書いたように, (ちゃんと実装すれば) O(mn^2) です.

しかし, 経験的にはもっと速く感じます.

続きを読む

ソースと実測 02:05

続きを読む

結論 02:05

ワーストケースはマジ死ぬ.

Dinic 法は使い所を間違えると辛い事になる.

例えば, 次のような条件が揃うとヤバめ.

  1. 問題の入力をうまくすれば, 最大流を求めなきゃいけないグラフを, 割と自由に決められる.
  2. 頂点数が 500 以下 みたいな, Dinic 法とかを過信した制約.

こういう時は, Goldberg-Tarjan とか, Push/Relabel 系のアルゴリズムを使った方がよさげ.

逆に,

  • 問題の入力から, 特殊な形のグラフを作って, その上で最大流を求める.

の場合は, 割と制約大きくても, Dinic のワーストケースを突くのが難しく, 大丈夫そう.

特に, 前に言った, 辺容量が全て同じ場合や, 二部グラフの場合など.


言い訳 and 次回予告 02:05

ゆるふわな感じに書いているのは, \TeX 記法が貧弱だからです, 許して下さい.

暇とやる気があれば, 次は O(n^3) のアルゴリズムについて書きます. 多分.

参考文献 02:05

1. は no title の一番上から読めます.

2. は Worst case behavior of the Dinic algorithm から読めます.

3. は Topcoder.

  1. Yefim Dinitz (2006), Dinitz' algorithm: the original version and even's version, In Theoretical Computer Science, Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman (Eds.), Springer-Verlag, pp.218-240.
  2. Gary R. Waissi (1991), Worst case behavior of the Dinic algorithm, Applied Mathematics Letters, vol.4, no.5, pp.57-60
  3. Zealint, Maximum Flow: Augmenting Path Algorithms Comparison, Algorithm Tutorials, TopCoder
  4. 秋葉拓哉, 岩田陽一, 北川宜稔 (2012), プログラミングコンテストチャレンジブック-第2版-~問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~, マイナビ

7747742015/10/15 23:28「Dinic 法と, その注意点」の注意2の部分について
探索順序は
S, a, b, a, e, a, S, b, e, b, f, b, S, c, g, T, g, c, h, T, h, c, S
ではないですか?最初に g に来たときに c に戻るのはなぜでしょうか.
私が理解していない/勘違いしていたら済みません.

Mi_SawaMi_Sawa2015/10/15 23:39(最初の b が d ですが)そのとおりですね. ご指摘ありがとうございます, 修正します.

2013-11-25ICPC2013 アジア地区予選 参加記

[]ICPC2013 アジア地区予選 会津大会 参加記 23:09

チーム Sophinyan として, ACM/ICPC アジア地区予選 会津大会に参加.

5完最下位の, 17位(チーム順位). 順位表

チーム順位大学順位国内チーム順位国内大学順位解いた問題数時間
17111375/10703

割と色んな人と喋れて, 楽しかった.

結果的には, 反省点はいくらでもあるけど, 当初の目標(去年のように Honorable Menthion にならず, 順位が欲しい)は達成出来て, 良かったと思う.

来年はもう少し上を目指したい.


例に依って参加記というよりただイベントを時系列順に並べた何かだが, とりあえず, 競技に関係する所だけ書こうと思う.

続きを読む