Hatena::Grouptopcoder

kohyatohの日記

 - 非数学系な人のTopCoder参加記です。

2011-02-19

SRM487 練習

| 08:03

Easy250BunnyComputer分割する
Medium550BunnyExam数学と見せかけて
Hard950BunnySequenceぎゃー

ばにーな回。




Easy 250 BunnyComputer

k+1ごとに独立にDP.

別にDPでなくてもアドホックに出来るけど、

自分はこういう場合DPのが書きやすい+自信があるので。


Medium 550 BunnyExam

答えは必ずm/k. (!!)

なので、与えられたlinkageが正しいものであるかのみ調べればよい。

グラフ彩色問題として考えれて、k>=4の場合は必ず塗れる。

k=1,2,3の場合はそれぞれ判別。


Hard 950 BunnySequence

cafelierさんの記事を参考に。

コラッツ木とか初めて知った。

木が再帰的な構造をしているのでDPできる。

一段目の1のノードが余分なので後で削除。


ソース

950が一番短い

Easy 250 BunnyComputer

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair

int dp[100];

class BunnyComputer {
public:
    int getMaximum(vector <int> p, int k) {
        int ans=0;
        rep(s, k+1) {
            vector<int> v;
            for(int i=s; i<(int)p.size(); i+=k+1) v.push_back(p[i]);
            memset(dp, 0, sizeof(dp));
            rep(i, v.size()) {
                if(i>0) dp[i+1] = max(dp[i], dp[i-1]+v[i]+v[i-1]);
                else dp[i+1] = dp[i];
            }
            ans += dp[v.size()];
        }
        return ans;
    }
};

Medium 550 BunnyExam

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair

int d[100];

class BunnyExam {
public:
    double getExpected(int m, int k, vector <int> g) {
        const int n=g.size()/2;
        rep(i, n) if(abs(g[i*2]-g[i*2+1])==1) return -1.0;
        if(k==1) {
            if(m>1) return -1.0;
        }
        else if(k==2) {
            rep(i, n) if(g[i*2]%2!=g[i*2+1]%2) return -1.0;
        }
        else if(k==3) {
            int nn=1;
            rep(i, n) nn*=3;
            rep(b, nn) {
                int p=b;
                rep(i, n) { d[i]=p%3; p/=3; }
                bool can=true;
                rep(i, g.size()) rep(j, g.size()) {
                    if(g[i]==g[j] && d[i/2]!=d[j/2]) can=false;
                    if(abs(g[i]-g[j])==1 && d[i/2]==d[j/2]) can=false;
                }
                if(can) return 1.0*m/k;
            }
            return -1.0;
        }
        return 1.0*m/k;
    }
};

Hard 950 BunnySequence

typedef long long Int;
#define MOD (1000000009LL)

Int S, dp[2000000];

class BunnySequence {
public:
    int getNumber(int m, int n) {
        S = dp[0] = 1;
        for(int i=1; i<=n; i++) {
            dp[i] = S;
            S = (S+dp[i])%MOD;
            if(i-m>=0) S = (S-dp[i-m]+MOD)%MOD;
        }
        Int ans=dp[n];
        if(n-m>=0) ans = (ans-dp[n-m]+MOD)%MOD;
        return ans;
    }
};

SRM486 練習

| 06:52

Easy300OneRegister若干めんどくさい
Medium450QuickSortDP
Hard1000BatmanAndRobin幾何!



Easy 300 OneRegister

ダイクストラ。ちゃんとやれば幅優先でもできる。

'/'の扱いに注意。


Medium 450 QuickSort

dp[a][b]:=Lのなかのa番目に大きい要素からb番目に大きい要素をQuickSortするときのコストの期待値。

順序が変わらないことを利用。


Hard 1000 BatmanAndRobin

2つの凸包の間には必ず直線を引ける。

その直線を凸包に当たるまでずらしたと考え、Batman側の点とRobin側の点を結ぶ線分で分ける。


ソース

Easy 300 OneRegister

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair

namespace std {
    bool operator<(const pair<long long, string>& l, const pair<long long, string>& r) {
        return l.second.size()!=r.second.size()
            ? l.second.size()>r.second.size()
            : l.second>r.second;
    }
}

class OneRegister {
public:
    string getProgram(int s, int t) {
        set<long long> vis;
        priority_queue<pair<long long, string> > q;
        q.push(mp(s, ""));
        if(s!=1) q.push(mp(1, "/"));
        while(!q.empty()) {
            pair<long long, string> v = q.top();
            q.pop();
            if(v.first==t) return v.second;
            if(v.first>t || vis.find(v.first)!=vis.end()) continue;
            vis.insert(v.first);
            q.push(mp(v.first*v.first, v.second+"*"));
            q.push(mp(v.first+v.first, v.second+"+"));
        }
        return ":-(";
    }
};

Medium 450 QuickSort

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair

int pos[100];
double dp[100][100];

class QuickSort {
public:
    double getEval(vector <int> L) {
        memset(dp, 0, sizeof(dp));
        const int n=L.size();
        rep(i, L.size()) pos[L[i]] = i;
        sort(L.begin(), L.end());
        for(int z=1; z<n; z++) {
            rep(a, n-z) {
                int b=a+z;
                for(int c=a; c<=b; c++) {
                    if(a<c-1) dp[a][b] += dp[a][c-1];
                    if(c+1<b) dp[a][b] += dp[c+1][b];
                    int t=0;
                    for(int k=a; k<c; k++) if(pos[L[k]]>pos[L[c]]) t++;
                    for(int k=c+1; k<=b; k++) if(pos[L[k]]<pos[L[c]]) t++;
                    dp[a][b] += t;
                }
                dp[a][b] /= z+1;
            }
        }
        return dp[0][n-1];
    }
};

Hard 1000 BatmanAndRobin

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair

#define X real
#define Y imag

typedef complex<double> P;
namespace std {
    bool operator<(const P& a, const P& b) {
        return X(a)!=X(b) ? X(a)<X(b) : Y(a)<Y(b);
    }
};
double cross(const P& a, const P& b) { return imag(conj(a)*b); }
double dot(const P& a, const P& b) { return real(conj(a)*b); }
int ccw(const P& a, P b, P c) {
    b-=a, c-=a;
    if(cross(b, c)>0) return 1;
    if(cross(b, c)<0) return -1;
    if(dot(b, c)<0) return +2;
    if(norm(b)<norm(c)) return -2;
    return 0;
}
double convex_area(vector<P> ps) {
    const int n=ps.size();
    int k=0;
    sort(ps.begin(), ps.end());
    vector<P> ch(2*n);
    for(int i=0; i<n; ch[k++]=ps[i++]) {
        while(k>=2 && ccw(ch[k-2], ch[k-1], ps[i])<=0) k--;
    }
    for(int i=n-2, t=k+1; i>=0; ch[k++]=ps[i--]) {
        while(k>=t && ccw(ch[k-2], ch[k-1], ps[i])<=0) k--;
    }
    k--;
    double area=0;
    for(int i=1; i<k-1; i++) area += 0.5*abs(cross(ch[i]-ch[0], ch[i+1]-ch[0]));
    return area;
}

class BatmanAndRobin {
public:
    double minArea(vector <int> x, vector <int> y) {
        const int n=x.size();
        if(n==1) return 0;
        double ans=1e100;
        vector<P> p;
        rep(i, n) p.push_back(P(x[i], y[i]));
        rep(i, n) rep(j, n) if(j!=i) {
            vector<P> b, r;
            b.push_back(p[i]);
            r.push_back(p[j]);
            rep(k, n) if(k!=i && k!=j) {
                if(ccw(p[i], p[j], p[k])>=0) b.push_back(p[k]);
                else r.push_back(p[k]);
            }
            double bs=convex_area(b), rs=convex_area(r);
            if(bs>=rs) ans=min(ans, bs);
        }
        return ans;
    }
};