Hatena::Grouptopcoder

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

 | 

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

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

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


テンプレ

だんだん追加されていく. 最終的にはこれくらい.

#include <bits/stdc++.h>
#define rep(i, n) for(signed i = 0; i < (n); ++i)
#define sz(v) ((signed)(v).size())
#define repsz(i, v) rep(i, sz(v))
#define aur auto &
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fst first
#define snd second
using namespace std;

A

本番は, solve が O(sz(a)^2) な貪欲に寄せてくるコードを書いていた.

int solve(vector<int> &a, vector<int> &b){
    if(accumulate(all(a), 0) != accumulate(all(b), 0)) return 1<<25;
    vector<int> aa[2], bb[2];
    repsz(i, a) aa[a[i]].eb(i);
    repsz(i, b) bb[b[i]].eb(i);
    int res = 0;
    rep(t, 2) repsz(i, aa[t]) res += abs(aa[t][i] - bb[t][i]);
    return res/2;
}
signed main(){
    int n, m; cin >> n >> m;
    vector<int> b(n), p(m);
    for(aur x : b) cin >> x;
    for(aur x : p) cin >> x;
    int res = 1<<25;
    rep(f, 2){
        vector<int> a;
        rep(i, m) rep(_, p[i]) a.eb((i + f) % 2);
        res = min(res, solve(a, b));
    }
    cout << res << endl;
    return 0;
}

B

本番は,

class {
    bool is_op, is_mul;
    int num;
};

みたいなものを書いていたけど, やってる事は同じだった.

signed main(){
    vector<int> a, b;
    string s; cin >> s;
    int target; cin >> target;
    repsz(i, s){
        if(s[i] == '+'){
            ++i;
            a.back() += s[i] - '0';
            b.eb(s[i] - '0');
        }else if(s[i] == '*'){
            ++i;
            a.back() *= s[i] - '0';
            b.back() *= s[i] - '0';
        }else{
            a.eb(s[i]-'0');
            b.eb(s[i]-'0');
        }
    }
    int A = accumulate(all(a), 0);
    int B = accumulate(all(b), 0);
    cout << ("IMLU"[(A==target)*2 + (B==target)]) << endl;
    return 0;
}

C

本番とたいして変わらないと思う.

signed main(){
    int n, m; cin >> n >> m;
    vector<int> v(n+1);
    rep(_, m){
        int c, d; cin >> c >> d;
        ++v[c]; --v[d];
    }
    int res = 0, now = 0;
    rep(i, n+1){
        now += v[i];
        res += now > 0 ? 3 : 1;
    }
    cout << res << endl;
    return 0;
}

D

本番とそんなには変わらないと思う. 入力の変数名がつらい.

放物線をいっぱい作るより, 障害物を mod バウンド幅 で寄せてくる方が楽だと思う.

二分探索とかせずに, 各障害物に対し, 超えるのに必要な, 放物線の極値の高さを求めていく方針.

typedef double R;
const R EPS = 1E-6;
const R INF = 1E30;
signed main(){
    cout << fixed << setprecision(10);
    R d;
    int n, bmax;
    cin >> d >> n >> bmax;
    vector<R> pos(n), ht(n);
    rep(i, n) cin >> pos[i] >> ht[i];
    R result = INF;
    rep(b, bmax+2) if(b){
        R w = d / b;
        R h = 0;
        rep(i, n){
            R x = pos[i] - ((int)(pos[i]/w+EPS)*w);
            h = max(h, ht[i] / (4 * (x/w - x*x/w/w)));
        }
        R vy = sqrt(2 * h);
        R vx = w / (2 * vy);
        R res = sqrt(vx * vx + vy * vy);
        if(vx > vy) res = sqrt(w);
        result = min(result, res);
    }
    cout << result << endl;
    return 0;
}

E

本番は, g を 点 -> 隣の点 で持ってたけど, 点 -> 辺の向き で持ってもよい気がして, 今回はそうしてみた.

typedef complex<int> P;
#define X real()
#define Y imag()
namespace std{ bool operator<(const P &a, const P &b){
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
}}
P dirs[] = { P(1, 0), P(0, 1), P(-1, 0), P(0, -1) };
P get_dir(){
    char c; cin >> c;
    string s = "ENWS";
    rep(i, 4) if(s[i] == c) return dirs[i];
    assert(false); return P(0, 0);
}
signed main(){
    int n, x, y, q;
    cin >> n >> x >> y >> q;
    P start(x, y);
    map<P, vector<P>> g;
    rep(i, n){
        int xx, yy; cin >> x >> y >> xx >> yy;
        P s(x, y), t(xx, yy);
        P dir = (t - s) / (abs(x-xx) + abs(y-yy));
        while(s != t){
            g[s].eb(dir);
            g[s+dir].eb(-dir);
            s += dir;
        }
    }
    typedef pair<P, P> State;
    set<State> now;
    rep(di, 4) now.insert(State(start, dirs[di]));
    rep(_, q){
        int d; cin >> d;
        rep(turn, d){
            set<State> nex;
            for(aur s : now) for(aur dir : g[s.fst]){
                if(turn){ // 今の向きじゃなくてもいい
                    if(dir != -s.snd) nex.insert(State(s.fst + dir, dir));
                }else{
                    if(dir ==  s.snd) nex.insert(State(s.fst + dir, dir));
                }
            }
            swap(now, nex);
        }
        P target = get_dir();
        set<State> nex;
        for(aur s : now){
            for(aur dir : g[s.fst]){
                if(target == s.snd){ // 回転前から O.K.
                    if(target != -dir) nex.insert(State(s.fst, dir));
                }else{
                    if(target == dir and dir != -s.snd) nex.insert(State(s.fst, dir));
                }
            }
        }
        swap(now, nex);
    }
    set<P> res;
    for(aur s : now) res.insert(s.fst);
    for(aur p : res) cout << p.X << " " << p.Y << endl;
    return 0;
}

F

本番とはちょっと方針が違う.

クラスカル法で unite の戻り値を使えるの, 良さがある.

struct UF{
    vector<int> par;
    UF(int n) : par(n, -1) {}
    void reset(){ fill(all(par), -1); }
    int find(int i){ return par[i] < 0 ? i : par[i] = find(par[i]); }
    int unite(int i, int j){
        if((i = find(i)) == (j = find(j))) return 0;
        if(par[i] > par[j]) swap(i, j);
        par[i] += par[j];
        par[j] = i;
        return 1;
    }
};
struct E{
    int s, t, c, use;
    bool operator<(const E &e) const { return c < e.c; }
    bool operator==(const E &e) const { return make_tuple(s, t) == make_tuple(e.s, e.t); }
};
using namespace rel_ops;

signed main(){
    int n, m; cin >> n >> m;
    vector<E> g(m);
    for(aur e : g){
        cin >> e.s >> e.t >> e.c;
        --e.s; --e.t;
    }
    sort(all(g));
    UF uf(n);
    int mst = 0;
    for(aur e : g) mst += e.c * (e.use = uf.unite(e.s, e.t));
    int res = 0, cnt = 0;
    for(aur e : g) if(e.use){
        uf.reset();
        int t = 0;
        for(aur ee : g) if(e != ee) t += ee.c * uf.unite(ee.s, ee.t);
        if(mst != t){ // 非連結な場合は mst より下がるハズなので無視してよい.
            res += e.c;
            ++cnt;
        }
    }
    cout << cnt << " " << res << endl;
    return 0;
}

G

本番は, Node に, 区間の左端と右端を持たせるスタイルでやっていた.

マクロ使うとすこしすっきりする.

const int INF = 1<<25;
struct SegTree{
    struct Node{
        int mn, lazy;
        Node() : mn(0), lazy(0) {}
    };
    vector<Node> tree;
    int N, offset;
    SegTree(const int n){
        N = 1;
        while(N < n) N <<= 1;
        tree.resize(N<<1);
    }
    void add(int l, int r, int v, int k, int ll, int rr){
        if(r <= ll || rr <= l) return;
        if(l <= ll && rr <= r){
            tree[k].lazy += v;
            return;
        }
        const int mm = (ll + rr) >> 1;
        add(l, r, v, k*2+1, ll, mm);
        add(l, r, v, k*2+2, mm, rr);
        tree[k].mn = min(
                tree[k*2+1].mn + tree[k*2+1].lazy,
                tree[k*2+2].mn + tree[k*2+2].lazy);
    }
    void add(int l, int r, int v){ add(l, r, v, 0, 0, N); }
    int mn(int l, int r, int k, int ll, int rr){
        if(r <= ll || rr <= l) return INF;
        if(l <= ll && rr <= r) return tree[k].mn + tree[k].lazy;
        const int mm = (ll + rr) >> 1;
        return tree[k].lazy + min(mn(l, r, k*2+1, ll, mm), mn(l, r, k*2+2, mm, rr));
    }
    int mn(int l, int r){ return mn(l, r, 0, 0, N); }
};

#define OPEN(i)  s[i] = '('; tree.add(i, n, +2); close.erase(i);
#define CLOSE(i) s[i] = ')'; tree.add(i, n, -2); close.insert(i);
signed main(){
    int n, q;
    cin >> n >> q;
    SegTree tree(n);
    string s; cin >> s;
    set<int> close;
    rep(i, n){
        if(s[i] == '('){
            tree.add(i, n, +1);
        }else{
            tree.add(i, n, -1);
            close.insert(i);
        }
    }
    int D = 1;
    while(D < n) D <<= 1;
    rep(_, q){
        int pos; cin >> pos; --pos;
        int res;
        if(s[pos] == '('){
            CLOSE(pos);
            res = *close.begin();
            OPEN(res);
        }else{
            OPEN(pos);
            res = 0;
            for(int d = D; d; d>>=1) if(res+d < n and tree.mn(res+d, n) < 2)
                res += d;
            ++res;
            CLOSE(res);
        }
        cout << ++res << endl;
    }
    return 0;
}

H

少し性質が特殊な気がして, やばいライブラリ使わなくても, わりと簡単に書ける気もする. (円と円の交点とかは候補点として取らないで済むし).

とはいえクソ長いので, 基本的なやつは自分のライブラリを使ってください. (交差判定とか距離とか1点を通る接線とか2円の共通接線とか)

bool ok(const L &s, const vector<C> &cs){
    for(aur c : cs) if(iD2Ss(c, s)) return false;
    return true;
}
bool ok(const P &p, const vector<C> &cs){
    for(aur c : cs) if(sgn(c.r, dPP(p, c.o)) > 0) return false;
    return true;
}

template<typename T> struct Zipper{
    map<T, int> zip;
    vector<T> unzip;
    const int operator[](const T &x){
        if(zip.count(x)) return zip[x];
        zip[x] = sz(unzip); unzip.eb(x);
        return zip[x];
    }
    const T operator()(const int &i) const { return unzip[i]; }
    typename vector<T>::const_iterator begin(){ return unzip.begin(); }
    typename vector<T>::const_iterator end(){ return unzip.end(); }
    int size(){ return zip.size(); }
};

struct E{
    int t; R c;
    E(int t, R c) : t(t), c(c) {}
};
signed main(){
    cout << fixed << setprecision(10);
    int n; cin >> n;
    P start(0, 0), goal; cin >> goal;
    vector<C> cs(n);
    rep(i, n){ cin >> cs[i].o; cs[i].r = (R)100; }
    Zipper<P> zip;
    zip[start]; zip[goal];
    vector<pair<int, int>> lines;
    if(ok(L(start, goal), cs)) lines.eb(zip[start], zip[goal]);
    rep(i, n){
        rep(t, 4) zip[cs[i].o + cs[i].r * polar((R)1, PI/2*t)];
        rep(j, n) if(i-j) if(iD2D2(cs[i], cs[j]))
            zip[cs[i].o + cs[i].r * (cs[j].o-cs[i].o) / dPP(cs[i].o, cs[j].o)];
        rep(j, i) for(aur l : lS1S1(cs[i], cs[j]))
            if(ok(l, cs)) lines.eb(zip[l.fst], zip[l.snd]);
        for(aur l : lS1P(cs[i], start))
            if(ok(l, cs)) lines.eb(zip[l.fst], zip[l.snd]);
        for(aur l : lS1P(cs[i], goal))
            if(ok(l, cs)) lines.eb(zip[l.fst], zip[l.snd]);
    }
    vector<vector<E>> g(sz(zip));
    for(aur pp : lines){
        g[pp.fst].eb(pp.snd, dPP(zip(pp.fst), zip(pp.snd)));
        g[pp.snd].eb(pp.fst, dPP(zip(pp.fst), zip(pp.snd)));
    }
    for(aur c : cs){
        vector<pair<R, int>> v;
        repsz(i, zip) if(sgn(c.r, dPP(zip(i), c.o)) == 0)
            v.eb(arg(zip(i)-c.o), i);

        sort(all(v));
        int i = 0, j = 1;
        repsz(_, v){
            if(ok(zip(v[i].snd), cs) and ok(zip(v[j].snd), cs)){
                g[v[i].snd].eb(v[j].snd, c.r * angle(c.o, zip(v[i].snd), zip(v[j].snd)));
                g[v[j].snd].eb(v[i].snd, c.r * angle(c.o, zip(v[i].snd), zip(v[j].snd)));
            }
            ++i; ++j; i%=sz(v); j%=sz(v);
        }
    }
    typedef tuple<R, int> State;
    priority_queue<State, vector<State>, greater<State>> pq;
    vector<R> d(sz(g), INF);
    pq.emplace(d[0] = 0, 0);
    while(!pq.empty()){
        R now; int u;
        tie(now, u) = pq.top(); pq.pop();
        if(sgn(now, d[u]) > 0) continue;
        for(aur e : g[u]) if(d[e.t] > now+e.c) pq.emplace(d[e.t] = now+e.c, e.t);
    }
    if(d[1] > INF/2) d[1] = 0;
    cout << d[1] << endl;
    return 0;
}

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/Mi_Sawa/20141021
 |