Hatena::Grouptopcoder

kohyatohの日記

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

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