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