Hatena::Grouptopcoder

kohyatohの日記

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

2011-01-20

SRM 481 練習

| 06:25

Easy250ChickenOracleやるだけ
Medium500BatchSystemRoulette数学っぽい
Hard900TicketPrintersなぜに900

Easy 250 ChickenOracle

「本当のことを教えられた人のうち、i人が嘘をついてる、として、矛盾がないかチェック」をi=1...(本当のことを教えられた人数), 鶏が本当の場合、卵が本当の場合でそれぞれ調べればよい。


Medium 500 BatchSystemRoulette

同じ人のjobはまとめて実行される。

jobの合計時間が短い人から実行され、合計時間が同じ人はランダムで順番が決まる。

同じ人のjob内での実行順序はランダム。

ランダムの場合の実行開始時間の期待値は、あるjobがそのjobの前に来る確率が1/2, 後に来る確率も1/2であることを利用すると簡単に計算できる。


Hard 900 TicketPrinters

基本

Printerの前を何もせずに通り過ぎる、というのは無駄なので、Printerの訪問順は左右にいったり来たりしながら広がっていく感じになる。

この訪問順の数はは初期位置の左側のプリンタの数をleft, 右側の数をrightとすると(left+right)C(left)で求められ、大体5000ぐらい。


Editorials解

全てのPrinterの訪問順を列挙し、それぞれに対して2分探索+最大マッチングでかかる時間を求め、minをとる。

(訪問順と目標時間が決まれば、「どのプリンタでどのチケットを印刷できるか」がわかるので、最大マッチングで印刷可能なチケットの枚数を求めることができる。よって、目標時間について2分探索を行えば、訪問順に対する最短時間が求まる。)

計算量は多分O(m * 30 * n^2)。(m=訪問順の数, 30は2分探索から)

訪問順はbitで生成。(0なら右に行き、1なら左に行く)


DP

wataさんの本番ソースを参考に。

dp[dir][l][b] := (使用済みプリンタ+今いるプリンタ)の左端が(初期位置-l), 右端が(初期位置+bitcount(b)-l)にあって、dir=0ならば現在左端におり、dir=1ならば右端にいる、という状態から、bの集合表現に含まれていないものを印刷するときの最短時間。

残りを印刷する時間は、(移動する時間)+(残りを最速で印刷する時間)で求められることを利用。

計算量はO(2^n * n^2)

dpの定義をうまくできなくてはまった。定義大事。


おまけ

DP解はプリンタ訪問順と最適解の地理的な関係を用いるのに対し、

Editorials解は訪問順と最適解の関係をぶったぎって別の問題として考えている。


個人的には、Editorials解の方が好き。(賢くなくてもわかるので)


ソース

Easy 250 ChickenOracle

こういう問題はなぜだか若干不安になる。

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

bool possible(int t, int f, int liar, int T, int F) {
    for(int i=0; i<=liar; i++) {
        int j=liar-i;
        if(i>T || j>F) continue;
        if(T-i+j==t && F-j+i==f) return true;
    }
    return false;
}

class ChickenOracle {
public:
    string theTruth(int n, int eggCount, int lieCount, int liarCount) {
        bool egg = possible(eggCount, n-eggCount, liarCount, n-lieCount, lieCount);
        bool chicken = possible(n-eggCount, eggCount, liarCount, n-lieCount, lieCount);
        if(egg && chicken) return "Ambiguous";
        else if(egg) return "The egg";
        else if(chicken) return "The chicken";
        else return "The oracle is a lie";
    }
};

Medium 500 BatchSystemRoulette

durationをintで計算しててWAったのは秘密。

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

class BatchSystemRoulette {
public:
    vector <double> expectedFinishTimes(vector <int> duration, vector <string> user) {
        int n=duration.size();
        map<string, long long> us;
        rep(i, n) us[user[i]]+=duration[i];
        map<string, double> ud;
        for(map<string, long long>::iterator it=us.begin(); it!=us.end(); it++) {
            long long k=0, s=0;
            for(map<string, long long>::iterator jt=us.begin(); jt!=us.end(); jt++) {
                if(it->second>jt->second) s+=jt->second;
                else if(it->second==jt->second) k++;
            }
            ud[it->first] = s + it->second*(k-1)/2.0;
        }
        vector<double> ans;
        rep(i, n) {
            long long s=0;
            rep(j, n) if(i!=j && user[i]==user[j]) s+=duration[j];
            ans.push_back(ud[user[i]]+s/2.0+duration[i]);
        }
        return ans;
    }
};

Hard 900 TicketPrinters

Editorials解

書きやすかった。

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

#define INF (1<<30)

int n;

int g[16][16];
int vis[16], cvis, mat[16];
bool rec(int at) {
    if(at<0) return true;
    rep(i, n) if(g[at][i] && vis[i]!=cvis) {
        vis[i] = cvis;
        if(rec(mat[i])) {
            mat[i] = at;
            return true;
        }
    }
    return false;
}
int match() {
    memset(mat, -1, sizeof(mat));
    memset(vis, -1, sizeof(vis));
    int r=0;
    rep(i, n) {
        cvis = i;
        if(rec(i)) r++;
    }
    return r;
}

bool can(int x, const vector<int>& t, const vector<int>& sv, const vector<int>& wv) {
    rep(i, n) rep(j, n) g[i][j] = t[i]+abs(sv[i]-wv[j])+1 <= x;
    return match()==n;
}

int calc(const vector<int>& t, const vector<int>& sv, const vector<int>& wv) {
    int l=0, r=1<<30, mid;
    while(r-l>1) {
        mid = (l+r)/2;
        if(can(mid, t, sv, wv)) r=mid;
        else l=mid;
    }
    return r;
}

class TicketPrinters {
public:
    int minTime(int currentPrinter, vector <int> printerDistance, vector <int> startingValues, vector <int> wantedValues) {
        n=printerDistance.size()+1;
        vector<int> pos(1, 0);
        rep(i, n-1) pos.push_back(pos.back()+printerDistance[i]);
        int m=n-1, left=currentPrinter;
        int ans=INF, mm=1<<m, d=(1<<left)-1;
        while(d<mm) {
            int l=currentPrinter-1, r=currentPrinter+1, pre=currentPrinter;
            vector<int> t(1, 0), sv(1, startingValues[currentPrinter]);
            rep(i, m) {
                int cur = d&(1<<i) ? l-- : r++;
                t.push_back(t.back()+abs(pos[pre]-pos[cur]));
                sv.push_back(startingValues[cur]);
                pre = cur;
            }
            ans = min(ans, calc(t, sv, wantedValues));
            if(d==0) break;
            int x=d&-d; int y=d+x;
            d=((d&~y)/x>>1)|y;
        }
        return ans;
    }
};

DP

こっちのがコンパクトだけど、かかった時間はEditorials解とは比較にならないほど長い。

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

#define INF (1<<30)

int dp[2][16][65536], dl[16][2][16];

class TicketPrinters {
public:
    int minTime(int cur, vector <int> pd, vector <int> sv, vector <int> wv) {
        rep(i, 2) rep(j, 16) rep(k, 65536) dp[i][j][k]=INF;
        int n=sv.size();
        vector<int> pos(1, 0);
        rep(i, n-1) pos.push_back(pos.back()+pd[i]);
        int nn=1<<n, left=cur, right=n-cur-1;
        for(int k=n-1; k>=0; k--) rep(dir, 2) {
            rep(l, left+1) {
                int r=k-l;
                if(r<0 || r>right) continue;
                int z=dir?cur+r:cur-l;
                int d=(1<<k)-1;
                while(d<nn) {
                    rep(i, n) if(!(d&(1<<i))) {
                        int nc=INF, mc=abs(wv[i]-sv[z])+1;
                        if(l==left && r==right) nc=0;
                        if(l<left) nc=min(nc, dp[0][l+1][d|(1<<i)]+pos[z]-pos[cur-l-1]);
                        if(r<right) nc=min(nc, dp[1][l][d|(1<<i)]+pos[cur+r+1]-pos[z]);
                        dp[dir][l][d] = min(dp[dir][l][d], max(nc, mc));
                    }
                    if(d==0) break;
                    int x=d&-d; int y=d+x;
                    d=((d&~y)/x>>1)|y;
                }
            }
        }
        return dp[0][0][0];
    }
};