Hatena::Grouptopcoder

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

 | 

2013-07-12

■ [ICPC]ICPC2013 国内予選 22:46

23:48 Eを追記.

19位4問229分13765秒
AAC9分583秒
BAC28分1711秒
C1WA, AC51(+20)分3126(+1200)秒
DAC119分7145秒

チーム Sophinyan で出ていました.

Cの1WAは提出ミス.

A 整長方形

出力が150*150以内なので, 全探索する.

#include <iostream>
#include <iomanip>
#include <map>
#include <cmath>
using namespace std;

#define mp make_pair
#define snd second
#define fst first

bool solve(){
    int h, w;
    cin >> h >> w;
    if(!(h|w)) return false;

    pair<int, pair<int, int> > res;
    res.fst = 1000000;
    for(int i = 1; i <= 150; ++i){
        for(int j = i+1; j <= 150; ++j){
            if(i*i + j*j > h*h + w*w
                    || (i*i + j*j == h*h + w*w && i > h)){
                res = min(res, mp(i*i+j*j, mp(i, j)));
            }
        }
    }
    cout << res.snd.fst << " " << res.snd.snd << endl;

    return true;
}

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

B ICPCの順位付け

適当にやってもバグらせる気しかしなかったので, わりとちゃんと書いた.

適当に書く時間+バグらせる確率*修正にかかる時間 > ちゃんと書く時間.

struct S{
    int team_num;
    vi wa, ac;
    int time;
    pair<int, int> get() const {
        pair<int, int> res(0, time);
        rep(i, wa.size()){
            if(ac[i]){
                ++res.fst;
                res.snd += wa[i] * 20;
            }
        }
        return res;
    }
    bool operator<(const S& o) const {
        pair<int, int> a = get(), b = o.get();
        if(a.fst != b.fst) return a.fst > b.fst;
        if(a.snd != b.snd) return a.snd < b.snd;
        return team_num > o.team_num;
    }
    bool operator==(const S& o){
        pair<int, int> a = get(), b = o.get();
        return a == b;
    }
};
bool solve(){
    int M, T, P, R;
    cin >> M >> T >> P >> R;
    if(!M) return false;
    vector<S> team(T);
    rep(i, T){
        team[i].team_num = i+1;
        team[i].wa.resize(P);
        team[i].ac.resize(P);
        team[i].time = 0;
    }

    rep(i, R){
        int m, t, p, j;
        cin >> m >> t >> p >> j;
        --t; --p;
        if(j == 0){
            team[t].ac[p] = 1;
            team[t].time += m;
        }else{
            team[t].wa[p] += 1;
        }
    }
    //rep(i, T){
    //    pair<int, int> a = team[i].get();
    //    cout << a.fst << ", " << a.snd << endl;
    //}
    sort(team.begin(), team.end());
    rep(i, T){
        if(i != 0){
            if(team[i-1] == team[i]){
                cout << "=";
            }else{
                cout << ",";
            }
        }
        cout << team[i].team_num;
    }
    cout << endl;
    //return false;
    return true;
}

C 階層民主主義

問題の理解にちょっと手間取った.

string s;
ll dfs(int l, int r){
    //cout << l << ", " << r << ": ";
    //cout << s.substr(l, r-l+1) << endl;
    if(s[l] == '[' && s[l+1] == '['){
        vector<ll> a;
        int depth = 0;
        int nl = l+1;
        for(int i = l+1; i < r; ++i){
            if(isdigit(s[i])) continue;
            if(s[i] == '['){
                if(depth == 0){
                    nl = i;
                }
                ++depth;
                continue;
            }
            if(s[i] == ']'){
                --depth;
                if(depth == 0){
                    a.pb(dfs(nl, i));
                }
            }
        }
        sort(all(a));
        ll res = 0;
        for(int i = 0; i < sz(a)/2+1; ++i) res += a[i];
        return res;
    }else{
        ++l;
        ll t = 0;
        while(isdigit(s[l])){
            t *= 10;
            t += s[l] - '0';
            ++l;
        }
        //cout << t << endl;
        return (t+1)/2;
    }
}

bool solve(){
    cin >> s;
    cout << dfs(0, s.size()-1) << endl;
    return true;
}

D 素数洞穴

螺旋の, 下, 左, 右の移動をガチで書いた.

Project Eulerで普通の螺旋は何度か書いた事があったが, バグが酷かった事を思い出して, こんな感じにした.

実際は, １つ出来たらあとはコピペして修正するだけ.

問題の図を睨みながら, 数列を決定して, 1から30くらいまで出力して図と一致するか確かめる.

今思ったけど, complex<int> をキーにしたmapで持てば, 結構マシそう…

vi sieve(int mx){
    ++mx;
    vi f(mx, true);
    f[0] = f[1] = false;
    for(int p = 2; p < mx; ++p){
        if(f[p]) for(int q = p+p; q < mx; q += p) f[q] = false;
    }
    return f;
}

int sq(int n){
    int m = sqrt(n);
    if((m+1)*(m+1) <= n) ++m;
    if(m*m == n) --m;
    if(m%2 == 0) --m;
    return m+2;
}
int sita(int n){
    if(n == 1) return 8;
    int s = sq(n);
    int t = s-2;
    if(t*t+1 == n) return s*s;
    if(t*t+s-1 == n) return n-1; // 右上
    if(t*t+s+s-2 == n) return n+1; // 左上
    if(t*t+s+s+s-3 == n) return n+s*4+3; // 左下
    if(s*s == n) return n+s*4+3;          // 右下

    if(t*t+s-1 >= n) return n-1; // 右の辺
    if(s*s-s+1 <= n) return n+s*4+3; // 下の辺
    if(t*t+s+s-2 <= n) return n+1; // 左の辺
    return n-4*s+9; // 上の辺
}
int hidari(int n){
    if(n == 1) return 6;
    int s = sq(n);
    int t = s-2;
    if(t*t+1 == n) return n-1;
    if(t*t+s-1 == n) return n+1; // 右上
    if(t*t+s+s-2 == n) return n+s*4+1; // 左上
    if(t*t+s+s+s-3 == n) return n+s*4+1; // 左下
    if(s*s == n) return n-1;          // 右下

    if(t*t+s-1 >= n) return n-s*4+11; // 右の辺
    if(s*s-s+1 <= n) return n-1; // 下の辺
    if(t*t+s+s-2 <= n) return n+s*4+1; // 左の辺
    return n+1; // 上の辺
}
int migi(int n){
    if(n == 1) return 2;
    int s = sq(n);
    int t = s-2;
    //if(t*t+1 == n) return n-1;
    if(t*t+s-1 == n) return n+s*4-3; // 右上
    if(t*t+s+s-2 == n) return n-1; // 左上
    if(t*t+s+s+s-3 == n) return n+1; // 左下
    if(s*s == n) return n+1;          // 右下

    if(t*t+s-1 >= n) return n+s*4-3; // 右の辺
    if(s*s-s+1 <= n) return n+1; // 下の辺
    if(t*t+s+s-2 <= n) return n-s*4+7; // 左の辺
    return n-1; // 上の辺
}

vi pflg;

bool solve(){
    //cout << sita(16) << endl;
    //return false;
    //rep(i, 30) cout << i << ": " << sita(i) << endl;
    //return false;

    int m, n;
    cin >> m >> n;
    if(!(m|n)) return false;
    set<int> q, r;
    vector<pair<int, int> > res(m+1);
    q.insert(n);
    res[n].fst = pflg[n];
    res[n].snd = pflg[n] ? n : 0;
    while(!q.empty()){
        foreach(it, q){
            int t = *it;
            //if(pflg[t]) cout << t << endl;
            //cout << t << endl;
            int s;
            s = sita(t);
            //cout << " -> " << s << endl;
            if(s <= m){
                if(pflg[s]) res[s] = max(res[s], mp(res[t].fst+1, s));
                else        res[s] = max(res[s], res[t]);
                r.insert(s);
            }
            s = migi(sita(t));
            //cout << " -> " << s << endl;
            if(s <= m){
                if(pflg[s]) res[s] = max(res[s], mp(res[t].fst+1, s));
                else        res[s] = max(res[s], res[t]);
                r.insert(s);
            }
            s = hidari(sita(t));
            //cout << " -> " << s << endl;
            if(s <= m){
                if(pflg[s]) res[s] = max(res[s], mp(res[t].fst+1, s));
                else        res[s] = max(res[s], res[t]);
                r.insert(s);
            }
        }
        swap(q, r);
        r.clear();
    }
    pair<int, int> tmp = *max_element(all(res));
    cout << tmp.fst << " " << tmp.snd << endl;
    return true;
}

E つながれた風船

本番が終わってから, ねじれの位置であることを考慮していなかった事に気づいた.

書くと, こんな感じ. (サンプルは通っている)

typedef long double R;
typedef complex<R> P;
#define X real()
#define Y imag()
const R EPS = 1E-10;
const R INF = 1E100;

typedef pair<P, P> L;

struct C{
    P o;
    R r;
    C(){}
    C(P a, R b): o(a), r(b){ }
};
R dot(P a, P b){ return real(conj(a) * b); }
P vec(L l){ return l.snd - l.fst; }

P hLP(L l, P p){
    return l.fst + dot(p - l.fst, vec(l)) / norm(vec(l)) * vec(l);
}

R dPP(P a, P b){ return abs(a - b); }
pair<P, P> pS1S1(C a, C b){
    R d = dPP(a.o, b.o);
    R rc = (d*d + a.r*a.r - b.r*b.r) / (2*d);
    R rs = sqrt(a.r*a.r - rc*rc);
    P dir = (b.o - a.o) / d;
    return mp(a.o + dir*P(rc, rs), a.o + dir*P(rc, -rs));
}

C f2(C a, C b){
    pair<P, P> x = pS1S1(a, b);
    C res;
    res.o = (x.fst + x.snd) / R(2);
    res.r = dPP(x.fst, x.snd) / R(2);
    return res;
}
C f3(C a, C b, C bb){
    b = f2(b, bb);
    P v = (bb.o-b.o) * P(0, 1);
    C c;
    c.o = hLP(L(b.o, b.o+v), a.o);
    c.r = sqrt(a.r * a.r - dPP(a.o, c.o)*dPP(a.o, c.o));
    return f2(b, c);
}
R d3(C a){
    return sqrt(norm(a.o) + a.r * a.r);
}

bool solve(){
    int n; cin >> n;
    if(!n) return false;
    vector<C> in(n);
    rep(i, n) cin >> in[i].o.X >> in[i].o.Y >> in[i].r;
    vector<C> candidate;
    rep(i, n) candidate.pb(in[i]);
    rep(i, n) rep(j, i) candidate.pb(f2(in[i], in[j]));
    rep(i, n) rep(j, i) rep(k, j) candidate.pb(f3(in[i], in[j], in[k]));
    R res = 0;
    repsz(_, candidate){
        C c = candidate[_];
        bool f = true;
        rep(i, n){
            P v = in[i].o - c.o;
            if(d3(C(v, c.r)) > in[i].r+EPS) f = false;
        }
        if(f) res = max(res, c.r);
    }
    cout << res << endl;

    return true;
}
コメントを書く

ゲスト



トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/Mi_Sawa/20130712
リンク元
 |