Hatena::Grouptopcoder

kohyatohの日記

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

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