blue_jamのTopCoder日記

SRM495 Div1 Easy

SRM, Practice | 00:35

概要

275点問題．

1からNまでの数を素数は赤，それ以外は青で塗ったカードがある．カードの部分集合を取り出し昇順に並べる．

色の並びだけで，数値を特定できるところはその数に，それ以外のところは-1を出力．

解法

DPだよDP．

dp[i][j]:=カードのi番目から数値j以上の数字のうち，文字列に適合する数値の数

もし，jがカードに適合しないカードであれば，

dp[i][j] = dp[i][j+1]　…(1)

カードが適合するならば，メソッドを再帰的に呼び出し，結果が1以上であれば，

dp[i][j] = dp[i+1][j+1] + dp[i][j+1]…(2)

結果が0であれば，(1)と同じ．

適合するカードは保存しておく（上書きしてもいい）

dp[i][1]が1なら，保存しておいた数値を返し，それ以外なら-1を返す．

class ColorfulCards {
public:
    bool isPrime[1001];
    int dp[50][1001];
    void init(){
        memset(dp, -1, sizeof(dp));

        isPrime[0] = isPrime[1] = false;
        for(int i=2;i<=1000;++i){
            bool flag = true;
            for(int j=2;j*j<=i;++j){
                flag = flag && i % j != 0;
            }
            isPrime[i] = flag;
        }
    }
    int recur(int idx, int next, int N, string &colors, vector<int> &res){
        int num = 0;
        if(idx == colors.size()) return true;
        if(next > N) return false;
        if(dp[idx][next] != -1){
            return dp[idx][next];
        }
        if(isPrime[next] && colors[idx] == 'R' || !isPrime[next] && colors[idx] == 'B'){
            if(recur(idx + 1, next + 1, N, colors, res)){
                res[idx] = res[idx] == 0 ? next : -1;
                num = 1;
            }
        }
        num = num + recur(idx, next + 1, N, colors, res);
        dp[idx][next] = num;
        return num;
    }
    vector <int> theCards(int N, string colors) {
        vector <int> res(colors.size(), 0);
        init();
        recur(0, 1, N, colors, res);
        return res;
    }
};

実は解説書く直前に今回書いた解法を思いついた．

その前は，2次元のvectorとlower_bound使ってDPの代わりやってた．

class ColorfulCards {
public:
    bool isPrime[1001];
    bool checked[50][1001];
    vector<vector<int> > dp;
    void init(){
        memset(checked, 0, sizeof(checked));

        isPrime[0] = isPrime[1] = false;
        for(int i=2;i<=1000;++i){
            bool flag = true;
            for(int j=2;j*j<=i;++j){
                flag = flag && i % j != 0;
            }
            isPrime[i] = flag;
        }
    }
    bool recur(int idx, int next, int N, string &colors){
        bool res;
        if(idx == colors.size()) return true;
        if(next > N) return false;
        if(checked[idx][next]){
            return lower_bound(dp[idx].begin(), dp[idx].end(), next) != dp[idx].end();
        }
        checked[idx][next] = true;
        res = false;
        if(isPrime[next] && colors[idx] == 'R' || !isPrime[next] && colors[idx] == 'B'){
            res = recur(idx + 1, next + 1, N, colors);
            if(res) dp[idx].push_back(next);
        }
        bool tmp = recur(idx, next + 1, N, colors);
        res = res || tmp;
        return res;
    }
    vector <int> theCards(int N, string colors) {
        vector <int> res;
        init();
        dp.clear();
        dp.resize(N);
        recur(0, 1, N, colors);
        for(int i=0;i<colors.size();++i){
            if(dp[i].size() == 1){
                res.push_back(dp[i][0]);
            }
            else{
                res.push_back(-1);
            }
        }
        return res;
    }
};