SRM 552 Div2

練習

250 TheProgrammingContestDivTwo
簡単なほうから貪欲。どうしてそれでよいかというと、仮に2問とけるときに、A,Bが残っていて、
ABのとき、A+(A+B)であり、B->Aのとき、B+(B+A)であるから。

class TheProgrammingContestDivTwo{
public:
    vector <int> find(int T, vector <int> requiredTime){
        int N = requiredTime.size();
        int solved = 0;
        sort(all(requiredTime));
        int rett = 0;
        for(int i=0;i<N;i++){
            int s = 0;
            int t = 0;
            int now = 0;
            for(int j=0;j<=i;j++){
                s += requiredTime[j];
                t += now + requiredTime[j];
                now += requiredTime[j];
            }
            if(s <= T){
                solved = i+1;
                rett = t;
            }
        }
        vector<int> ret(2);
        ret[0] = solved;
        ret[1] = rett;
        return ret;
    }
};

500 TheLotteryBothDivs
より強いsuffixを残すように削除した後、prefixの数を数えるだけ。
suffixかどうかの判定についてはもっとよい方法があると思う。

ll mpow10(ll x){
    ll ret = 1;
    for(int i=0;i<x;i++){
        ret *= 10;
    }
    return ret;
}
class TheLotteryBothDivs{
public:
    double find(vector <string> goodSuffixes){
        sort(all(goodSuffixes));
        goodSuffixes.erase(unique(all(goodSuffixes)),goodSuffixes.end());
        for(int i=0;i<goodSuffixes.size();i++){
            reverse(all(goodSuffixes[i]));
        }
        bool update = true;
        while(update){
            update = false;
            for(int i=0;i<goodSuffixes.size();i++){
                for(int j=0;j<goodSuffixes.size();j++){
                    if(i == j) continue;
                    if(goodSuffixes[i].size() <= goodSuffixes[j].size()) continue;
                    for(int k=0;k<goodSuffixes[i].length();k++){
                        if(goodSuffixes[i].substr(0,k) == goodSuffixes[j]){
                            goodSuffixes.erase(goodSuffixes.begin()+i);
                            update = true;
                            goto updated;
                        }
                    }
                }
            }
updated:
        {}
        }
        ll good = 0;
        for(int i=0;i<goodSuffixes.size();i++){
            good += mpow10(9-goodSuffixes[i].size());
        }
        return 1.0 * good / 1000000000;
    }
};

1000 TheCowDivTwo
動的計画法だった。dp[とった数][Nで割った余り]。
どうしてこうやって更新しているかというと、もしdp[N][とった数][Nで割った余り]とすると
メモリが足りないから。
N=1000,K=47で、N*N*K=47000000だからギリギリ。

int MOD = 1000000007;

class TheCowDivTwo{
public:
    int find(int N, int K){
        vector<vector<int> > dp(K+1,vector<int>(N));
        dp[0][0] = 1;
        for(int i=0;i<N;i++){
            vector<vector<int> > pre = dp;
            for(int j=0;j<K;j++){
                for(int l=0;l<N;l++){
                    dp[j+1][(l+i)%N] += pre[j][l];
                    dp[j+1][(l+i)%N] %= MOD;
                }
            }
        }
        return (int)dp[K][0];
    }
};