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 までを解きなおしてみました.

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


続きを読む

AmibzDructAmibzDruct2018/07/09 07:48casino online <a href="https://onlinecasinoplay.us.org/">online casino gambling</a> online casino real money <a href=" https://onlinecasinoplay.us.org/">gsn casino</a> | <a href=https://onlinecasinoplay.us.org/>online casino games</a> <a href=https://onlinecasinoplay.us.org/>casino slots</a>

m7ikotpdm7ikotpd2018/07/09 14:33roulette games - <a href="https://roulettecas.com/">roulette free</a>
play roulette for free <a href=" https://roulettecas.com/ ">free roulette games</a>
https://roulettecas.com/

Bad Credit Bad Credit 2018/07/09 15:32instant loans no credit check <a href="http://aloan.cars">business loan</a> need a loan with bad credit <a href=http://aloan.cars>payday loans surrey bc</a>

Payday Express Payday Express 2019/03/02 06:59<a href="https://loansforbadcredit2019.com/">small loans for bad credit</a>

ifxtnxfzojxdifxtnxfzojxd2019/05/06 01:35http://pakforum.net/viewtopic.php?t=67994

uikgaykxqrsauikgaykxqrsa2019/05/06 03:38http://pakforum.net/viewtopic.php?t=67994

jjgtgrczskdljjgtgrczskdl2019/05/08 12:55http://bitly.com/mstiteli-hd

xrimxnswcqbkxrimxnswcqbk2019/05/08 12:59http://bitly.com/mstiteli-hd

pfpfsmbmxjdtpfpfsmbmxjdt2019/05/08 13:54http://bitly.com/mstiteli-hd

eydrmdonzfueeydrmdonzfue2019/05/08 14:35http://bitly.com/mstiteli-hd

wqehatquxuftwqehatquxuft2019/05/08 14:39http://bitly.com/mstiteli-hd

MatSmElayMatSmElay2019/05/08 14:45Doxycycline Acutane [url=http://via100mg.com]viagra[/url] Como Usar Dapoxetina Levitra Rxlist Stop Propecia Trop Cher

wtpkrwnqmwaewtpkrwnqmwae2019/05/08 15:03http://bitly.com/mstiteli-hd

edlzmbnendkcedlzmbnendkc2019/05/08 15:52http://bitly.com/mstiteli-hd

pkarcmtbyangpkarcmtbyang2019/05/08 16:10http://bitly.com/mstiteli-hd

vvbolykquetsvvbolykquets2019/05/08 16:44http://bitly.com/mstiteli-hd

hzefjnkbnnjshzefjnkbnnjs2019/05/23 08:37Мстители 4 http://135.it/xfiXI Мстители смотреть
<a href="http://135.it/xfiXI">Мстители финал </a>

htulrsyqxkcjhtulrsyqxkcj2019/05/23 11:04Мстители 4 http://135.it/xfiXI Мстители кино
<a href="http://135.it/xfiXI">Мстители финал 4</a>

cvzyvirgdjrrcvzyvirgdjrr2019/05/23 11:23Мстители 4 http://135.it/xfiXI Мстители кино
<a href="http://135.it/xfiXI">Мстители финал </a>

gaivbnsnfwlcgaivbnsnfwlc2019/05/23 11:54Мстители 4 http://135.it/xfiXI Мстители полностью
<a href="http://135.it/xfiXI">Мстители финал 4</a>

cxarxgrmnlrbcxarxgrmnlrb2019/05/23 13:24Мстители 4 http://135.it/xfiXI Мстители кино
<a href="http://135.it/xfiXI">Мстители 2019 финал 4</a>

ldjvabghkontldjvabghkont2019/05/29 09:48http://grupotir.com/component/k2/itemlist/user/42621
l4452k l14974u r12390p

nnkioanwjgeinnkioanwjgei2019/05/29 09:58http://grupotir.com/component/k2/itemlist/user/42621
j3811w e7226p k9754q

emzeahwmkcjaemzeahwmkcja2019/05/29 12:39http://grupotir.com/component/k2/itemlist/user/42621
n11606p g14199k y10237t

vimhbpgfwutbvimhbpgfwutb2019/05/29 15:17http://grupotir.com/component/k2/itemlist/user/42621
r5759i f285n j9468x

ehbfnfbhvysbehbfnfbhvysb2019/05/29 16:57http://grupotir.com/component/k2/itemlist/user/42621
o12469d u11057v k2063u

elxasgjikkgrelxasgjikkgr2019/05/29 16:58http://grupotir.com/component/k2/itemlist/user/42621
p14376m o5094k v5400g

rmnbdoznmikgrmnbdoznmikg2019/06/02 13:13http://bitly.com/2Wv7LU6

qfwpyoptzzcaqfwpyoptzzca2019/06/03 12:03http://bitly.com/2Wv7LU6

fpozzkfzoxqcfpozzkfzoxqc2019/06/03 12:18http://bitly.com/2Wv7LU6

ntxwseflqbjdntxwseflqbjd2019/06/04 12:51http://bitly.com/315GTcG

nhkkluohbznhnhkkluohbznh2019/06/04 22:39http://bitly.com/315GTcG

sjlnqircigjdsjlnqircigjd2019/06/04 23:51http://bitly.com/315GTcG

nqwgjgglmmlbnqwgjgglmmlb2019/06/05 00:40http://bitly.com/315GTcG

wganvqutvehiwganvqutvehi2019/06/05 02:02http://bitly.com/315GTcG

fqmbtqfrlddvfqmbtqfrlddv2019/06/05 02:02http://bitly.com/315GTcG

bdriqvtnkmtybdriqvtnkmty2019/06/05 02:25http://bitly.com/315GTcG

isxcxxqzncpgisxcxxqzncpg2019/06/05 02:31http://bitly.com/315GTcG

tirdpmjnjjdotirdpmjnjjdo2019/06/05 18:57http://bitly.com/315GTcG

llaeuxpazgpsllaeuxpazgps2019/06/05 19:25http://bitly.com/315GTcG

xygwntyxuzamxygwntyxuzam2019/06/05 21:22http://bitly.com/315GTcG

bqkezfhmwemhbqkezfhmwemh2019/06/05 23:09http://bitly.com/315GTcG

ufpygonphbmqufpygonphbmq2019/06/05 23:27http://bitly.com/315GTcG

wqlmopsvvtdowqlmopsvvtdo2019/06/08 08:10http://bitly.com/315GTcG

ggxssvodpxdsggxssvodpxds2019/06/08 10:31http://bitly.com/315GTcG

cvaizjvrgvtlcvaizjvrgvtl2019/06/08 12:30http://bitly.com/315GTcG

LesTushLesTush2019/08/21 08:25Expired Amoxil How To Get Cialis Without Doctor [url=http://boijoy.com]prix du levitra effets secondaires[/url] Macrobid Tablets Medication Cash Delivery Online

pjboqzfoosnqpjboqzfoosnq2019/08/24 08:53t8553d c4489d f12869w VIDEO http://bitly.com/2KSmsKf watch

gwjwuwvqyonhgwjwuwvqyonh2019/08/24 10:08i1461c i9929v c14746m VIDEO http://bitly.com/2P9AIlS watch

ninrvlcqlslxninrvlcqlslx2019/08/24 14:01i13372r v807f x10533m VIDEO http://bitly.com/2Zsd3ko watch

yeqilqiswrisyeqilqiswris2019/08/24 14:48z3308g p11463k x11678i VIDEO http://bitly.com/2Hl3Dgq watch

yubbxkqztyyayubbxkqztyya2019/08/27 00:19r13415z a7061m x7412u VIDEO https://00-tv.com/sitemap/sitemap3187.php watch

dlbzqlyaemiwdlbzqlyaemiw2019/08/27 00:35w915l o8218r k7776w VIDEO https://00-tv.com/sitemap/sitemap7993.php watch

quajdgpzmrbvquajdgpzmrbv2019/08/27 01:03h10577x r231h g1722w VIDEO http://clck.ru/HnRLe watch

fzababjczuaafzababjczuaa2019/08/27 03:04t843u v12063v c3779s VIDEO https://00-tv.com/sitemap/sitemap1687.php watch

zkpyzygvbyqmzkpyzygvbyqm2019/08/27 03:43v492p f11119l q13003x VIDEO https://00-tv.com/sitemap/sitemap14829.php watch

zvfqcsonfucyzvfqcsonfucy2019/08/27 03:48r2280p p6989u l6030c VIDEO https://00-tv.com/sitemap/sitemap995.php watch

tiobmnxyaujdtiobmnxyaujd2019/08/27 03:53w13509q x1261r k13215r VIDEO https://00-tv.com/sitemap/sitemap3091.php watch

qpbsypevxdnzqpbsypevxdnz2019/08/27 04:18t471m m14536m x734q VIDEO https://00-tv.com/sitemap/sitemap10002.php watch

oahutbszdsbioahutbszdsbi2019/08/27 04:23a3117q o4440l t14753u VIDEO https://00-tv.com/sitemap/sitemap11458.php watch

rxheaoywwklqrxheaoywwklq2019/08/27 11:47h13584a p1698x u14055h VIDEO https://00-tv.com/sitemap/sitemap15775.php watch

fyfmpriitebefyfmpriitebe2019/08/27 11:55l12881k h949o i13901k VIDEO https://00-tv.com/sitemap/sitemap1919.php watch

gppwdkdotkomgppwdkdotkom2019/08/27 12:44m8029m w1294c r11444a VIDEO https://00-tv.com/sitemap/sitemap6125.php watch

rzycxcotztvwrzycxcotztvw2019/08/27 13:49s2942v k3608q b1608b VIDEO https://00-tv.com/sitemap/sitemap13780.php watch

fcpxmrqqqiwvfcpxmrqqqiwv2019/08/27 14:09m11455v b12854u f2977v VIDEO https://00-tv.com/sitemap/sitemap6563.php watch

gvlusgxyjaocgvlusgxyjaoc2019/08/27 14:53g9242m b12823k e12430j VIDEO https://00-tv.com/sitemap/sitemap6294.php watch

fvoqrhewgodwfvoqrhewgodw2019/08/27 15:15q97a m12454j f5112f VIDEO https://00-tv.com/sitemap/sitemap13828.php watch

fqkndgmzpwczfqkndgmzpwcz2019/08/27 16:17f10683v z13936n a12013s VIDEO http://clck.ru/HnRME watch

ybittyzwsuucybittyzwsuuc2019/08/27 17:18w6171t r9690u v5801r VIDEO https://00-tv.com/sitemap/sitemap2744.php watch

vxnroxqdgsodvxnroxqdgsod2019/08/27 18:15z11127n j8502w w7738x VIDEO https://00-tv.com/sitemap/sitemap4304.php watch

lcdhmnebivxjlcdhmnebivxj2019/08/27 18:43a11198a c6392b l10641h VIDEO https://00-tv.com/sitemap/sitemap4356.php watch

jcjeurwunclqjcjeurwunclq2019/08/27 19:10e11303t w5517k l1239r VIDEO http://bitly.com/325cBGM watch

rkpdkpcrroyirkpdkpcrroyi2019/08/27 19:44a11024w f13094s h665z VIDEO https://00-tv.com/sitemap/sitemap14883.php watch

locnktjffsnylocnktjffsny2019/08/27 20:34h14059a a6960e l7481b VIDEO https://00-tv.com/sitemap/sitemap5829.php watch

cbyxuktloxeacbyxuktloxea2019/08/27 20:42t10075r r10875q s8523a VIDEO https://00-tv.com/sitemap/sitemap8457.php watch

zbihbtltgxxpzbihbtltgxxp2019/08/27 20:48y5040g s2136r r6361q VIDEO https://00-tv.com/sitemap/sitemap10477.php watch

edbavkjplhwiedbavkjplhwi2019/08/27 21:43m6488a v7002x a1606p VIDEO https://00-tv.com/sitemap/sitemap14287.php watch

llorqttorhfdllorqttorhfd2019/08/27 23:32l4456z g8926b f13226e VIDEO https://00-tv.com/sitemap/sitemap7261.php watch

oneebwynzstdoneebwynzstd2019/08/28 00:44b8292m k2458m l847g VIDEO https://00-tv.com/sitemap/sitemap14951.php watch

gcarwxpxbfeqgcarwxpxbfeq2019/08/28 01:41b8832o z1610m k10378f VIDEO https://00-tv.com/sitemap/sitemap2879.php watch

rdqscskwupqwrdqscskwupqw2019/08/28 02:24r8316r b12383i s4081z VIDEO https://00-tv.com/sitemap/sitemap11827.php watch

viarakulokpiviarakulokpi2019/08/28 04:44h7352h a6889s i4579p VIDEO https://00-tv.com/sitemap/sitemap15722.php watch

epcsahjfnewyepcsahjfnewy2019/08/28 06:13c8418l h10814a q4821x VIDEO https://00-tv.com/sitemap/sitemap874.php watch

hohcnndznatihohcnndznati2019/08/28 09:15n14800n u1536f k3378y VIDEO https://00-tv.com/sitemap/sitemap2925.php watch

ksjqzsrljnglksjqzsrljngl2019/08/28 09:29e293i q6314q i6832d VIDEO https://00-tv.com/sitemap/sitemap11255.php watch

tiysxpbbixxetiysxpbbixxe2019/08/28 10:32y6476u d14073l q7226m VIDEO https://00-tv.com/sitemap/sitemap13486.php watch

beyaoybzuzipbeyaoybzuzip2019/08/28 11:23g10066s p5921f p12904p VIDEO https://00-tv.com/sitemap/sitemap8230.php watch

lapmatqizkdplapmatqizkdp2019/08/28 12:32k12305b a14275f t12062b VIDEO https://00-tv.com/sitemap/sitemap4006.php watch

btsgnquvijdtbtsgnquvijdt2019/08/28 13:54e10718j e1341o e11369k VIDEO https://00-tv.com/sitemap/sitemap9241.php watch

hyuivaefnxhrhyuivaefnxhr2019/08/28 15:37r8030k w9297z z1374j VIDEO https://00-tv.com/sitemap/sitemap6478.php watch

zdfirumqqawdzdfirumqqawd2019/08/28 15:58p10399z b11634j q9288q VIDEO https://00-tv.com/sitemap/sitemap13822.php watch

zjyqdayuoujizjyqdayuouji2019/08/28 18:12x3504y p6197s l14730o VIDEO https://00-tv.com/sitemap/sitemap11812.php watch

ywqgqhmxsijvywqgqhmxsijv2019/08/28 19:06s14237c j2019o k11756c VIDEO https://00-tv.com/sitemap/sitemap8919.php watch

dtuyfyqnphkudtuyfyqnphku2019/08/28 19:54b7919g u4505k y2292o VIDEO https://00-tv.com/sitemap/sitemap5762.php watch

rnamyasaxwalrnamyasaxwal2019/08/28 22:17p2394i q14906t g10555j VIDEO https://00-tv.com/sitemap/sitemap3992.php watch

swhuiehrcnzkswhuiehrcnzk2019/08/29 00:59x8990o r2647p o6941s VIDEO https://00-tv.com/sitemap/sitemap7374.php watch

eglzmtwogiokeglzmtwogiok2019/08/29 02:02t1505q s13564s a8423r VIDEO https://00-tv.com/sitemap/sitemap5893.php watch

ovleywmerypfovleywmerypf2019/08/29 02:55q3287q b7594e l6488v VIDEO https://00-tv.com/sitemap/sitemap2387.php watch

vuqawkmzjmuevuqawkmzjmue2019/08/29 03:59y5300t x8331x q8467g VIDEO https://00-tv.com/sitemap/sitemap1608.php watch

gklipnakxafbgklipnakxafb2019/08/29 05:02y5795u l14877q b53t VIDEO https://00-tv.com/sitemap/sitemap14923.php watch

obwhjnhlbdzzobwhjnhlbdzz2019/08/29 06:58l6347t c6072s f10267v VIDEO https://00-tv.com/sitemap/sitemap10415.php watch

utmswawtxchvutmswawtxchv2019/08/29 07:55q12346a r4589p z7368x VIDEO https://00-tv.com/sitemap/sitemap8339.php watch

rgcgxapstrpfrgcgxapstrpf2019/08/29 12:06x1225e f11818h p2146x VIDEO https://00-tv.com/sitemap/sitemap8311.php watch

prhmelwwlefgprhmelwwlefg2019/08/29 13:05w1539y c2247b i4116z VIDEO https://00-tv.com/sitemap/sitemap3113.php watch

jeovxdmgmkltjeovxdmgmklt2019/08/29 15:47i5751h e2583n e9361f VIDEO https://00-tv.com/sitemap/sitemap10929.php watch

hlupxsjjdqsshlupxsjjdqss2019/08/29 17:49o10760k e7980r l1280y VIDEO https://00-tv.com/sitemap/sitemap2003.php watch

yxrcdkulcccbyxrcdkulcccb2019/08/29 20:43u7228k q1180k a12688w VIDEO https://00-tv.com/sitemap/sitemap2988.php watch

bnbjazmwshbbbnbjazmwshbb2019/08/29 21:48t12219k z11002d f6310q VIDEO https://00-tv.com/sitemap/sitemap1712.php watch

oeaietfakfzjoeaietfakfzj2019/08/29 23:47c931s m4465x j420t VIDEO https://00-tv.com/sitemap/sitemap11429.php watch

tfcuxusegntatfcuxusegnta2019/08/30 00:58r6328p q3863c g4441j VIDEO https://00-tv.com/sitemap/sitemap9488.php watch

qgcjnbhjbgzlqgcjnbhjbgzl2019/08/30 02:06s9449k k9714t n1740y VIDEO https://00-tv.com/sitemap/sitemap4141.php watch

snyitiepwlhtsnyitiepwlht2019/08/30 02:47n2556x e8181u r2400o VIDEO https://00-tv.com/sitemap/sitemap12825.php watch

gdnnpsbyqknlgdnnpsbyqknl2019/08/30 04:45z11892w k13994x x3412c VIDEO https://00-tv.com/sitemap/sitemap3734.php watch

hfcdhdfoynohhfcdhdfoynoh2019/08/31 04:03e14820n l12486r k1148b VIDEO https://inlove.org.ua/redirect?url=http://4serial.com watch

rsxlkrukxljdrsxlkrukxljd2019/08/31 04:15n9894f v8155w p8353w VIDEO http://3tpartners.com/__media__/js/netsoltrademark.php?d=4serial.com watch

jqjnchqtcdfqjqjnchqtcdfq2019/08/31 06:12k5842p b7312p p1140r VIDEO http://gladstonemutual.com/__media__/js/netsoltrademark.php?d=4serial.com watch

mvktvamnrqcrmvktvamnrqcr2019/08/31 08:16b6904t r4574a j13443a VIDEO http://npdialogue.com/__media__/js/netsoltrademark.php?d=4serial.com/ watch

xbqnfbdakhlxxbqnfbdakhlx2019/08/31 09:09u8594j l4234j r6127o VIDEO http://sanjuancollege.com/__media__/js/netsoltrademark.php?d=4serial.com watch

dlxlcgynznkxdlxlcgynznkx2019/08/31 10:49x14491l u10260g x4720t VIDEO http://www.engetec.it/__media__/js/netsoltrademark.php?d=4serial.com watch

fofddrtfizqcfofddrtfizqc2019/08/31 11:41k13026d s4463d z1517w VIDEO http://www.tianyaxiaozhan.com/home/link.php?url=https://4serial.com watch

drdpaqniwbgrdrdpaqniwbgr2019/08/31 13:15s9625r v2454c r8469h VIDEO http://cartogra.net/__media__/js/netsoltrademark.php?d=4serial.com watch

cjzzopzsbczhcjzzopzsbczh2019/08/31 13:53p4716j p10825m l12937d VIDEO http://flatratebooks.com/__media__/js/netsoltrademark.php?d=4serial.com watch

edpvlfqrtdpdedpvlfqrtdpd2019/08/31 14:06k6162s p4859y k14982q VIDEO http://gondasportsinvestments.com/__media__/js/netsoltrademark.php?d=4serial.com watch

ymanjvdxyrpuymanjvdxyrpu2019/08/31 15:44w14435k k10771e p4560l VIDEO http://osteraas.com/__media__/js/netsoltrademark.php?d=4serial.com watch

xxcthsxpzvzkxxcthsxpzvzk2019/08/31 19:02w2857p o810v t4034j VIDEO https://maps.google.cat/url?q=http://4serial.com watch

frfryxdowrusfrfryxdowrus2019/08/31 19:53y79n u8268o z10184z VIDEO http://autotrademarkofarlington.com/__media__/js/netsoltrademark.php?d=4serial.com watch

qfgoxfpsxrxqqfgoxfpsxrxq2019/08/31 20:40g4046a u13322v p13027k VIDEO http://copierconnection.com/__media__/js/netsoltrademark.php?d=4serial.com watch

rtroekacwmeurtroekacwmeu2019/08/31 22:18b1064f o12624c j13104k VIDEO http://laredomorningtimes.info/__media__/js/netsoltrademark.php?d=4serial.com watch

yxbpwwtkrdoryxbpwwtkrdor2019/09/01 00:46l3511i n2326o s4672m VIDEO http://www.heronpublishing.com/__media__/js/netsoltrademark.php?d=4serial.com watch

xahcbewhrvaxxahcbewhrvax2019/09/01 02:19s4970j s2279e b8379d VIDEO http://discount-foto.ru/bitrix/redirect.php?event1=&event2=&event3=&goto=https://4serial.com watch

ixonuhameixonuhame2019/09/17 22:56[url=http://mewkid.net/order-amoxicillin/]Amoxicillin 500 Mg[/url] <a href="http://mewkid.net/order-amoxicillin/">Amoxicillin 500mg Capsules</a> cil.fgpn.topcoder.g.hatena.ne.jp.iws.xp http://mewkid.net/order-amoxicillin/

msoqadukudopmsoqadukudop2019/09/17 23:21[url=http://mewkid.net/order-amoxicillin/]Amoxicillin[/url] <a href="http://mewkid.net/order-amoxicillin/">Buy Amoxicillin</a> ctn.usup.topcoder.g.hatena.ne.jp.idl.jm http://mewkid.net/order-amoxicillin/

MichaelDiuctMichaelDiuct2019/10/05 04:59m-dnc.com

ticjaputicjapu2019/10/05 05:014serial.com

MichaelDiuctMichaelDiuct2019/10/05 05:32https://m-dnc.com/vd/will-ferrell-film-dan-acara-tv

MichaelDiuctMichaelDiuct2019/10/05 06:06https://m-dnc.com/vd/aplikasi-download-film-untuk-laptop

mwmjqdymwmjqdy2019/10/05 08:054serial.com

AtkpyhigAtkpyhig2019/10/11 07:12https://m-dnc.com/vd/download-our-glamorous-time-sub-indo

AynyukjpAynyukjp2019/10/12 03:59http://bitly.com/zahar-berkut-2019-movies zahar-berkut-2019-movies <a href="http://bitly.com/zahar-berkut-2019-movies">Zakhar Berkut 2 movies</a>
http://bitly.com/zahar-berkut-2019-movies
[url=http://bitly.com/zahar-berkut-2019-movies]Захар Беркут p movies[/url]

srfmr926srfmr9262019/10/13 09:10http://www.colorofshare.com/index.php?topic=54844.0
sdgrfse3423

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 にならず, 順位が欲しい)は達成出来て, 良かったと思う.

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


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

続きを読む