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

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

2011-01-31

SRM484 練習

| 11:16

Easy250RabbitNumber実験したもの勝ち
Medium550PuyoPuyo脳みそクラッシュ
Hard950NumberMagic数学...

りんごさんの難しい回。

Editorialsがすごい参考になる。



Easy 250 RabbitNumber

4以上の数字を含む数は考えなくて良いらしい。


Medium 550 PuyoPuyo

見た目ストレートにDPできそうだが、底に何かある時と何もない時で異なる扱いをしなければならず、難しい。


dp[i][j] := 底に溜まっているぷよを最短j手で消し切れ、残りi個落ちてくる、という状況から消し切れる場合の数

とすると、不思議なことにうまくいくらしい。

ぷよの積み方を、消し切る最短手で分類する、という発想がすごいと思う。



もうすこし泥臭い方法としては、底にぷよが一つもないときのみ特殊なことを考慮して、

dp1[i][j] := 底に同じ色のぷよがj個貯まっているところから、i個落ちてきた後に初めて消し切る場合の数 (ただしj>0)

dp2[i] := 底に何もないところから、i個落ちてきた後(初めてとは限らず)消し切る場合の数

とすれば、2段のDPで解ける。


Hard 950 NumberMagic

元ネタの手品みたいに、基数が何か絡むのかと思ったら、そんなことはなかった。


minT(N, K) := k枚カードを用意したとき、1..Nを判別できるようにするのに必要な、カードに書かれた数字の数の最小値(ただし、カードに空白があってもよいとする)

なる関数を考え、minT(N, K)<=M*K<=N*K-minT(N, K)を満たす最小のKを二分探索で求めればよい、らしい。


一回問題から離れて、どのカードに何個数字を載せるかは自由として、逆に数字ごとに何枚のカードに載せるかが決まっているとして考えてみる。

この時、1,2,3,4を4枚のカードに、一つの数字を1枚のカードのみに載せて判別しようとしたら、

1 -> 1枚目にだけ載せる

2 -> 2枚目にだけ載せる

3 -> 3枚目にだけ載せる

4 -> 4枚目にだけ載せる

とすれば判別できる。

また、1,2,3,4,5を4枚のカードに、一つの数字を2枚のカードに載せて判別しようとしたら、

1 -> 1枚目と2枚目に載せる

2 -> 1枚目と3枚目に載せる

3 -> 1枚目と4枚目に載せる

4 -> 2枚目と3枚目に載せる

5 -> 2枚目と4枚目に載せる

とすれば判別できる。

このように、一般に、k枚中t枚のカードに載せることによって、kCt個の数字を判別することができる。

(0枚に載せる、つまり全く載せないことによっても、1個の数字は判別できることに注意。)


次に、どのカードに何個数字を載せるか、数字ごとに何枚のカードに載せるかが自由として、全カードに載せてある数字の個数の合計を最小化することを考える。この時の最小値がminT(N, k)。

これは、0枚に載せてkC0=1個の数字を判別させ、1枚に載せて別のkC1=k個の数字を判別させ...というのを、累計がNを越えるまで続ければよい。

例えば、N=4, K=4なら、'1'を0枚に載せ、'2','3','4'を1枚に載せればよいので、minT(4, 4)=3。


何枚のカードに載せるかを適当にシフトすれば、空白を埋めていくことができるので、

minT..N*K-minTの中の任意の個数の数字をカード全体に載せることができる。

よって、本題では一つのカードには必ずM個の数字を載せると決めてあるので、minT(N, K)<=M*K<=N*K-minT(N, K)となるようなKを探せばよい。

minT(N, K)はKに対して単調減少なので、2分探索を使って上の式を満たす最小のKを求めることができる。


ソース

ソースだけ見れば、ほんとに数行のコードなのに、どうしてこうも難しいんだろう...

Easy 250 RabbitNumber

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

int S(long long a) { int c=0; while(a) { c+=a%10; a/=10; } return c; }

class RabbitNumber {
public:
    int theCount(int low, int high) {
        int ans=0;
        rep(d, (1<<18)+1) {
            long long x=0;
            rep(i, 10) { x*=10; x+=(d>>(18-2*i))%4; }
            if(low<=x && x<=high) ans += S(x)*S(x)==S(x*x);
        }
        return ans;
    }
};

Medium 550 PuyoPuyo

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

#define MOD (1000000007LL)

long long dp[2000][2000];

class PuyoPuyo {
public:
    int theCount(int L, int N) {
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        rep(i, N) {
            dp[i+1][0] = 4*dp[i][L-1]%MOD;
            rep(j, N) dp[i+1][j+1] = (dp[i][j]+3*dp[i][j+L])%MOD;
        }
        return dp[N][0];
    }
};

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

#define MOD (1000000007LL)

long long dp1[2000][20], dp2[2000];

class PuyoPuyo {
public:
    int theCount(int L, int N) {
        memset(dp1, 0, sizeof(dp1));
        dp1[0][L] = 1;
        for(int i=1; i<=N; i++) for(int j=1; j<L; j++) {
            dp1[i][j] = dp1[i-1][j+1];
            for(int k=2; k<i; k++) {
                dp1[i][j] = (dp1[i][j]+3*dp1[k-1][1]*dp1[i-k][j])%MOD;
            }
        }
        for(int i=2; i<=N; i++) {
            dp2[i] = 4*dp1[i-1][1];
            for(int k=2; k<i; k++) {
                dp2[i] = (dp2[i]+4*dp1[k-1][1]*dp2[i-k])%MOD;
            }
        }
        return dp2[N];
    }
};

Hard 950 NumberMagic

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

Int C(int n, int k) { Int r=1; rep(i, k) r=r*(n-i)/(i+1); return r; }

Int minT(int n, int k) {
    Int r=0, done=0;
    rep(i, k+1) {
        Int t = C(k, i);
        if(n-done<=t) return r+i*(n-done);
        else r+=t*i, done+=t;
    }
    return LLONG_MAX;
}

class NumberMagic {
public:
    int theMin(int N, int M) {
        int l=0, r=N;
        while(r-l>1) {
            Int mid = (l+r)/2;
            if(minT(N, mid)<=min(M, N-M)*mid) r=mid;
            else l=mid;
        }
        return r;
    }
};

2011-01-29

SRM483 練習

| 04:03

Easy250BestApproximationDiv1いやらしいです
Medium500Bribesみたまんまbit DP
Hard900Sheep数学?

Easy 250 BestApproximationDiv1

B<=1000なので全て試せばよい。

誤差の扱いが若干めんどくさい。


Medium 500 Bribes

influence<=500なので、9離れると500/(2^9)=0となり影響がなくなる。

なので前8人と自分と後8人を覚えてbit DPすればよい。


Hard 900 Sheep

本番の時は、2分探索で何百人も落ちていた。

ボートの容量Cで渡し切れても、C+1で渡し切れるとは限らない。(羊の選び方が悪いので。)

しかし、計算すると、調べるべきボートの容量はある程度限られることがわかる。


ボートの容量をCとする。

この時、全ての羊を運び切れるなら、C*maxRuns>=sum(w[1..n])とならなければならないので、sum(w[1..n])/maxRuns<=C。

よって、C<sum(w[1..n])/maxRunsならば絶対運びきれないので、調べるだけ無駄。


また、k番目に重い羊を運べないとすると、(C-w[k])*maxRuns<sum(w[1..k-1])が成立するはずなので、逆にC>=sum(w[1..n])/maxRuns+max(w[1..n])ならば必ず全ての羊を運べる。

なので、C>=sum(w[1..n])+max(w[1..n])の時は運び切れることがハナから分かっているので、これも調べるだけ無駄。


よって、C=sum(w[1..n])/maxRuns~sum(w[1..n])/maxRuns+max(w[1..n])の範囲のみ、運び切れるか調べればよい。

運びきれるかどうかは、setかmapを使って一つあたりO(nlogn)でシミュレーションできる。


この問題に限らないけど、数学的/論理的な裏付けが分かってしまえば、コード自体は簡単至極、という問題がHardには多い気がする。


ソース

Easy 250 BestApproximationDiv1

sprintf.

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

char buf[1000], ans[1000];

class BestApproximationDiv1 {
public:
    string findFraction(int maxDen, string number) {
        int ansX=-1, ansA=0, ansB=0;
        for(int b=1; b<=maxDen; b++) rep(a, b) {
            sprintf(buf, "%d", a*1000000/b);
            string s(buf);
            s = "0."+string(6-s.size(), '0')+s;
            int x=1;
            while(x<7 && s[x+1]==number[x+1]) x++;
            if(x>ansX) ansX=x, ansA=a, ansB=b;
        }
        sprintf(ans, "%d/%d has %d exact digits", ansA, ansB, ansX);
        return ans;
    }
};


Medium 500 Bribes

実装を簡単にするために、checkとnxtの更新を分けている。

分けずにやるとO(2^16)でできるらしいけど、まあ2倍だし。

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

int bitcount(int a) { int c=0; while(a>0) a&=a-1, c++; return c; }
int dp[2][200000];

class Bribes {
public:
    int minBribes(vector <int> f, vector <int> r) {
        const int n=f.size(), B=1<<17, INF=100;
        int *cur=dp[0], *nxt=dp[1];
        rep(i, B) cur[i]=bitcount(i);
        rep(i, n) {
            // check
            rep(b, B) if(cur[b]<INF) {
                int s=0;
                rep(k, 17) if(b&(1<<k)) {
                    int d=8-k;
                    if(0<=i+d && i+d<n) s+=f[i+d]/(1<<abs(d));
                }
                if(s<r[i]) cur[b]=INF;
            }
            // nxt
            rep(b, B) nxt[b]=INF;
            rep(b, B) {
                nxt[b*2%B] = min(nxt[b*2%B], cur[b]);
                nxt[b*2%B+1] = min(nxt[b*2%B+1], cur[b]+1);
            }
            swap(cur, nxt);
        }
        int ans=INF;
        rep(i, B) ans=min(ans, nxt[i]);
        return ans==INF ? -1 : ans;
    }
};

Hard 900 Sheep

コード的にはめちゃくちゃ簡単。

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

int n, r, w[3000];

int can(int v) {
    map<int, int> s;
    rep(i, n) s[-w[i]]++;
    rep(k, r) {
        int c=v;
        map<int, int>::iterator it;
        while(!s.empty() && (it=s.lower_bound(-c))!=s.end()) {
            c+=it->first;
            if(--it->second==0) s.erase(it);
        }
    }
    return s.empty();
}

class Sheep {
public:
    int minCapacity(int numSheep, int maxRuns, vector <string> part1, vector <string> part2, vector <string> part3, vector <string> part4) {
        n=numSheep, r=maxRuns;
        string str;
        rep(i, part1.size()) str+=part1[i];
        rep(i, part2.size()) str+=part2[i];
        rep(i, part3.size()) str+=part3[i];
        rep(i, part4.size()) str+=part4[i];
        stringstream sin(str);
        rep(i, n) sin >> w[i];
        sort(w, w+n, greater<int>());
        int s=accumulate(w, w+n, 0);
        rep(i, 3000) if(can(s/r+i)) return s/r+i;
        return -1;
    }
};

2011-01-22

SRM 482 練習

| 14:59

Easy250LockersDiv1ねこだまし
Medium500HanoiGoodAndBad突き合わせ
Hard1000BalancingActむずい

Easy 250 LockersDiv1

シミュレーション。

一見TLEしそうだが、計算量はO(n*(1/1+1/2+1/3+...))=およそO(n\ln n)ぐらいで大丈夫。


Medium 500 HanoiGoodAndBad

Earlのやり方の場合、あるsolve_Earl呼び出しで動かすべき円がどこにあるかで、次の3つのsolve_Earl再帰のうちどれの途中にいるのかがわかるので、辿っていけばよい。


Hard 1000 BalancingAct

載せ方の表現

左右どちらの皿に載せるか/または全く載せないかは、重さに-1, 0, 1を掛けることで表せる。

よって、重りw1..wnの載せ方は、sum(coef[i]*w[i]) (coef[i]=-1,0,1)で「値として」表現することができる。


unlabeledの値がわかるか?

labeledとunlabeledからunlabeledの真の値を割り出せるかどうかは、次のように考えればよい。


まず、labeledとunlabeledについて、天秤に載せる載せ方を全列挙して、それぞれの載せ方での天秤の傾き方を記録する。

次に、unlabeledからいくつかの重りの重さを変えた、unlabeled'を用意し、labeledとunlabeled'について、これまた天秤に載せる載せ方を全列挙して、それぞれの載せ方での天秤の傾き方を記録する。

2つの記録を突き合わせてみて、2つが全く同じであるならば、天秤を使った実験をしてもunlabeledとunlabeled'は見分けられない、ということになる。


これを全てのunlabeled'について実行すれば、unlabeledの重さを特定できるかどうかがわかる。

もちろんunlabeled'のとり方は無限に近く(10^32-1通り)あるので、全部試すことはできないが、実はunlabeledの近くだけ調べれば十分らしい。(証明はわかりません。)


実装

「傾き方の記録」が同じかどうかは、unlabeledの載せ方全て(3^4通り)に対して、

(1)それより大きい値をとるlabeledの載せ方のうち、一番小さいものの値 - 1

(2)それより小さい値をとるlabeledの載せ方のうち、一番大きいものの値 + 1

の二つを記録しておき、unlabeled'での対応する載せ方について、(1)を上回ったり(2)を下回ったりしないか調べるだけでよい。

(同じ値をとるlabeledの載せ方がある場合は若干特別扱いして(1)=(2)=unlabeledの載せ方の値とみなせばよい。)

(1)(2)の値は、labeledを二つに分割して尺取り法を使えば、一つのunlabeledの載せ方に対して0(3^(n/2)) (n=len(labeled))で調べることができる。



unlabeled'については、unlabeledのそれぞれの値を-DELTA~+DELTAずらしたものについて調べればよい。

System Testを通るにはDELTAとして最低4必要。


計算量はO(3^m3^{n/2} + 3^md^mm) (n=len(labeled), m=len(unlabeled), d=2*DELTA+1)


ソース

Easy 250 LockersDiv1

配列再利用。

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

int a[3000000];

class LockersDivOne {
public:
    int lastOpened(int N) {
        rep(i, N) a[i]=i+1;
        int n=N, ans=1;
        for(int i=2; n>0; i++) {
            int k=0;
            rep(j, n) {
                if(j%i) a[k++]=a[j];
                else ans=a[j];
            }
            n=k;
        }
        return ans;
    }
};

Medium 500 HanoiGoodAndBad

長い割にやってることは少ない。

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

long long pow3[20];
int dave;
int h[3][20], x[3];

void solve_Dave(int s, int t, int p, int n) {
    if(dave==0) return ;
    if(n>0) {
        solve_Dave(s, p, t, n-1);
        if(dave==0) return ;
        x[s]--;
        h[t][x[t]++] = n;
        if(--dave==0) return ;
        solve_Dave(p, t, s, n-1);
    }
}

int solve_Earl(int s, int t, int p, int n) {
    if(n>0) {
        if(x[s]>0 && h[s][0]==n) {
            rep(i, x[s]-1) h[s][i]=h[s][i+1];
            x[s]--;
            return solve_Earl(s, t, p, n-1);
        }
        else if(x[p]>0 && h[p][0]==n) {
            rep(i, x[p]-1) h[p][i]=h[p][i+1];
            x[p]--;
            return pow3[n-1]+solve_Earl(t, s, p, n-1);
        }
        else if(x[t]>0 && h[t][0]==n) {
            rep(i, x[t]-1) h[t][i]=h[t][i+1];
            x[t]--;
            return 2*pow3[n-1]+solve_Earl(s, t, p, n-1);
        }
    }
    return 0;
}

class HanoiGoodAndBad {
public:
    int moves(int N, int Dave) {
        pow3[0]=1;
        rep(i, 19) pow3[i+1]=pow3[i]*3;
        x[0]=N, x[1]=0, x[2]=0;
        rep(i, N) h[0][i]=N-i;
        dave=Dave;
        solve_Dave(0, 1, 2, N);
        return solve_Earl(0, 1, 2, N);
    }
};

Hard 1000 BalancingAct

とても複雑だと思う。

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

#define INF (1LL<<60)
typedef long long Int;
#define DELTA (12)

int c[100], cf[100][4], ud[4];
Int l[100], r[100];

int mypow(int a, int x) { int r=1; rep(i, x) r*=a; return r; }

vector<Int> gen(vector<int> v) {
    const int n=v.size(), nn=mypow(3, v.size());
    vector<Int> r(nn, 0);
    rep(d, nn) {
        int p=d;
        rep(i, n) { r[d]+=(p%3-1)*v[i]; p/=3; }
    }
    sort(r.begin(), r.end());
    r.erase(unique(r.begin(), r.end()), r.end());
    return r;
}

class BalancingAct {
public:
    vector <string> recover(vector <int> labeled, vector <int> u) {
        const int n=labeled.size(), m=u.size();
        vector<int> lab[2];
        rep(i, n) lab[i<n/2].push_back(labeled[i]);
        vector<Int> a(gen(lab[0])), b(gen(lab[1]));
        const int mm=mypow(3, m), an=a.size(), bn=b.size();
        rep(d, mm) {
            int p=d;
            rep(i, m) { cf[d][i]=p%3-1; p/=3; }
        }
        rep(k, mm) {
            c[k]=0;
            rep(i, m) c[k]+=cf[k][i]*u[i];
            l[k]=-INF, r[k]=INF;
            int bi=bn-1;
            rep(ai, an) {
                while(bi>0 && c[k]<a[ai]+b[bi]) bi--;
                // hopefully a[ai]+b[bi]<=c[k], c[k]<a[ai]+b[bi+1]
                if(a[ai]+b[bi]==c[k]) l[k]=r[k]=c[k];
                if(a[ai]+b[bi]<c[k]) l[k] = max(l[k], a[ai]+b[bi]);
                if(bi+1<bn) r[k] = min(r[k], a[ai]+b[bi+1]);
            }
            if(l[k]<c[k]) l[k]++;
            if(r[k]>c[k]) r[k]--;
        }
        vector<string> ans(m, "yes");
        const int dd=mypow(2*DELTA+1, m);
        rep(d, dd) {
            int p=d;
            rep(i, m) { ud[i]=u[i]+p%(2*DELTA+1)-DELTA; p/=(2*DELTA+1); }
            rep(i, m) ud[i]=max(1, min(100000000, ud[i]));
            bool can=true;
            rep(k, mm) {
                c[k]=0;
                rep(i, m) c[k]+=cf[k][i]*ud[i];
                if(c[k]<l[k] || r[k]<c[k]) can=false;
            }
            if(can) rep(i, m) if(u[i]!=ud[i]) ans[i]="no";
        }
        return ans;
    }
};