Hatena::Grouptopcoder

kohyatohの日記

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

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