Hatena::Grouptopcoder

kohyatohの日記

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

2011-02-07

SRM485 練習

| 12:37

Easy250AfraidOfEven全探索
Medium500RectangleAvoidingColoring面倒
Hard1000Deposit幾何


Easy 250 AfraidOfEven

等差数列は最初の2項で残り全ての項が決まるので、1番目、2番目の要素のありうる値を全列挙し、それぞれに対して残りの要素が有効な値を取れるか調べればよい。


Medium 500 RectangleAvoidingColoring

条件を満たす四角形は少ない(短辺の長さが4以下など)ことを利用。

短辺の長さが1,2の場合はそれぞれ適当に求める。

短辺の長さが3,4の場合は、面積が24以下でないと条件を満たさないことを利用し、全探索する。

ものっそめんどくさい...


Hard 1000 Deposit

多角形の角しか目的地にはなりえないことに注意。

多角形の辺の上で、目的地が変わりうる点と、Depositと交差するかが変わりうる点を全部列挙し、それらの点で辺をぶつ切りにし、それぞれの線分について、目的地に向かう線がDepositと交差するか調べる。


目的地が変わりうる点<=>二つの目的地からの距離が等しい点

Depositと交差するかが変わりうる点<=>目的地(候補)とDepositの頂点を結んだ線上の点

である。


真面目にやればもう少しぶつ切りする点を減らせる気がするけど、時間的に間に合うのでキニシナイ。


幾何ライブラリSpaghetti Sourceのものを参考にさせていただきました。


Source

Easy 250 AfraidOfEven

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

bool is_power2(int a) {
    while(a%2==0) a/=2;
    return a==1;
}

class AfraidOfEven {
public:
    vector <int> restoreProgression(vector <int> seq) {
        const int n=seq.size();
        for(long long f=seq[0]; ; f*=2) {
            for(long long s=seq[1]; s<INT_MAX; s*=2) {
                bool can=true;
                long long d=s-f;
                for(int k=2; k<n; k++) {
                    long long t = f+d*k;
                    if(t<=0 || t>INT_MAX || t%seq[k] || !is_power2(t/seq[k])) {
                        can = false;
                        break;
                    }
                }
                if(can) {
                    vector<int> r;
                    rep(i, n) r.push_back(f+d*i);
                    return r;
                }
            }
        }
    }
};

Medium 500 RectangleAvoidingColoring

1000より長い500て。

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

int w, h, b[50][50], f[50][50];

long long calc_1() {
    int c=0;
    rep(i, w) c += b[i][0]<0;
    return 1LL<<c;
}

long long calc_2() {
    int cb2=0, cw2=0;
    rep(i, w) if(b[i][0]==0 && b[i][1]==0) cb2++;
    rep(i, w) if(b[i][0]==1 && b[i][1]==1) cw2++;
    if(cb2>1 || cw2>1) return 0;
    int c=0;
    rep(i, w) if(b[i][0]==-1 && b[i][1]==-1) c++;
    long long ans=1LL<<c;
    if(cb2==0) {
        rep(i, w) if(b[i][0]!=1 && b[i][1]!=1) {
            int c2=0;
            rep(j, w) if(j!=i && b[j][0]==-1 && b[j][1]==-1) c2++;
            ans += 1LL<<c2;
        }
    }
    if(cw2==0) {
        rep(i, w) if(b[i][0]!=0 && b[i][1]!=0) {
            int c2=0;
            rep(j, w) if(j!=i && b[j][0]==-1 && b[j][1]==-1) c2++;
            ans += 1LL<<c2;
        }
    }
    if(cb2==0 && cw2==0) {
        rep(ib, w) if(b[ib][0]!=1 && b[ib][1]!=1) {
            rep(iw, w) if(iw!=ib && b[iw][0]!=0 && b[iw][1]!=0) {
                int c2=0;
                rep(j, w) if(j!=ib && j!=iw && b[j][0]==-1 && b[j][1]==-1) c2++;
                ans += 1LL<<c2;
            }
        }
    }
    return ans;
}

long long rec(int r) {
    if(r==w) return 1;
    long long ans=0;
    rep(d, 1<<h) {
        rep(i, h) f[r][i] = (d>>i)&1;
        rep(i, h) if(b[r][i]>=0 && b[r][i]!=f[r][i]) goto fail;
        rep(i, r) rep(x, h) rep(y, x) {
            if(f[i][x]==f[i][y] && f[i][x]==f[r][x] && f[i][y]==f[r][y]) {
                goto fail;
            }
        }
        ans+=rec(r+1);
fail:;
    }
    return ans;
}

class RectangleAvoidingColoring {
public:
    long long count(vector <string> board) {
        w=board.size(), h=board[0].size();
        if(w>h) {
            rep(i, w) rep(j, h) {
                if(board[i][j]=='?') b[i][j]=-1;
                else b[i][j]=board[i][j]=='W';
            }
        }
        else {
            rep(i, w) rep(j, h) {
                if(board[i][j]=='?') b[j][i]=-1;
                else b[j][i]=board[i][j]=='W';
            }
            swap(w, h);
        }
        if(h==1) return calc_1();
        else if(h==2) return calc_2();
        else return w*h>24 ? 0 : rec(0);
    }
};

Hard 1000 Deposit

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

typedef complex<double> P;

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;
}

bool intersectSS(const P& s0, const P& s1, const P& t0, const P& t1) {
    return ccw(s0, s1, t0)*ccw(s0, s1, t1)<=0
        && ccw(t0, t1, s0)*ccw(t0, t1, s1)<=0;
}

class Deposit {
public:
    double successProbability(vector <int> siteX, vector <int> siteY, vector <int> depositX, vector <int> depositY) {
        const int n=siteX.size(), m=depositX.size();
        vector<P> p, q;
        rep(i, n) p.push_back(P(siteX[i], siteY[i]));
        rep(i, m) q.push_back(P(depositX[i], depositY[i]));
        double valid=0;
        rep(k, n) {
            P a(p[k]), b(p[(k+1)%n]);
            vector<double> v;
            v.push_back(0.0);
            v.push_back(1.0);
            rep(i, n) rep(j, i) {
                P c(0.5*(p[i]+p[j])), diff(p[j]-p[i]);
                P d(real(c)+imag(diff), imag(c)-real(diff));
                double s1=cross(d-c, a-c), s2=cross(d-c, b-c);
                if(s1*s2<0) v.push_back(s1/(s1-s2));
            }
            rep(i, n) rep(j, m) {
                double s1=cross(q[j]-p[i], a-p[i]), s2=cross(q[j]-p[i], b-p[i]);
                if(s1*s2<0) v.push_back(s1/(s1-s2));
            }
            sort(v.begin(), v.end());
            rep(i, v.size()-1) {
                P c(a+0.5*(v[i]+v[i+1])*(b-a));
                double md=-1;
                int mi=-1;
                rep(j, n) {
                    double d=norm(p[j]-c);
                    if(md<d) md=d, mi=j;
                }
                bool ok=false;
                rep(j, m) if(intersectSS(p[mi], c, q[j], q[(j+1)%m])) ok=true;
                if(ok) valid += abs((v[i+1]-v[i])*(b-a));
            }
        }
        double total=0;
        rep(i, n) total+=abs(p[i]-p[(i+1)%n]);
        return valid/total;
    }
};