Hatena::Grouptopcoder

kohyatohの日記

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

2011-01-17

SRM 480 練習

| 06:34

練習した回についても書いてみることにしました。


SRM 480 (div 1)

Easy250InternetSecurity実装問題
Medium450NetworkSecurityループがないので簡単
Hard1100StringDecryption難しい、というより面倒

Easy 250 InternetSecurity

シミュレーションするだけ。


Medium 450 NetworkSecurity

クライアントAについて、Aから行けるクライアント全てがsecureであれば、Aと、それらのクライアントを通って行けるサーバとのあいだには安全なルートがある。

よって、Aからは、他のクライアントを経ずに直接しか行けないサーバとの間にのみゲートを設ければよい。


Hard 1100 StringDecryption

"4351234324"を例に説明する。

一段目のデコードの時点で、"43"をひとつの塊として取り出した場合、これは"3333"となる。

このとき、"3333"+(残りの文字列のデコード結果)をもう一度デコードすることになるが、"3333"が"33"+"33"=>"333333"にデコードされることはないことに注目する("333333"は"63"とエンコードされるはずなので。)

このことより、"3333"は、"3333"のうち最大でひとつだけが(個数、数字)ペアの数字の部分として用いられ、残りは個数部分に用いられることがわかる。

"3333"のうち一つを数字部分として用いた場合、残りの"51234324"をデコードした後、最初の数字部分として'3'を用いることはできないことに注意すると、


dp[i][digit][v] := i番目の文字列をデコードして、digitが最初のペアの数字部分となる解の数。ただしv=0ならばその数字部分に対応する個数部分が完成しており、v=1ならば対応する個数部分が未完成(0が最初に来ているか、個数部分がない)


としてDPできる。計算量はO(n^2 * 10)。


なお、一段目のデコードでも、"4351234324"->"4351234"+"324"などにはデコードできないことに注意。(数時間これではまった...)


ソース

Easy 250 InternetSecurity

これ実装めんどくさい。

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair

int w[100], v[100];

class InternetSecurity {
public:
    vector <string> determineWebsite(vector <string> address, vector <string> keyword, vector <string> dangerous, int threshold) {
        int n=address.size();
        rep(i, n) w[i]=0;
        rep(i, n) v[i]=0;
        set<string> key[100];
        rep(i, n) {
            string s;
            stringstream sin(keyword[i]);
            while(sin>>s) key[i].insert(s);
        }
        set<string> dkey;
        rep(i, dangerous.size()) {
            dkey.insert(dangerous[i]);
            rep(k, n) if(key[k].find(dangerous[i])!=key[k].end()) w[k]++;
        }
        bool f;
        do {
            f = false;
            rep(i, n) if(w[i]>=threshold && v[i]==0) {
                f = true;
                v[i]=1;
                for(set<string>::iterator it=key[i].begin();
                        it!=key[i].end(); it++) {
                    if(dkey.find(*it)==dkey.end()) {
                        dkey.insert(*it);
                        rep(k, n) if(key[k].find(*it)!=key[k].end()) w[k]++;
                    }
                }
            }
        } while(f);
        vector<string> r;
        rep(i, n) if(v[i]) r.push_back(address[i]);
        return r;
    }
};

Medium 450 NetworkSecurity

再帰で簡単

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair

int n, m, ans;
int c[50][50], v[50];
vector<string> cc, sc;

void secure(int at) {
    if(v[at]) return;
    v[at] = 1;
    rep(i, m) c[at][i]=0;
    rep(i, n) if(cc[at][i]=='Y') {
        secure(i);
        rep(k, m) if(c[i][k]) c[at][k]=1;
    }
    rep(i, m) if(sc[at][i]=='Y' && c[at][i]==0) {
        c[at][i] = 1;
        ans++;
    }
}

class NetworkSecurity {
public:
    int secureNetwork(vector <string> clientCable, vector <string> serverCable) {
        cc=clientCable, sc=serverCable;
        ans = 0;
        n = cc.size();
        m = sc[0].size();
        rep(i, 50) v[i]=0;
        rep(i, n) secure(i);
        return ans;
    }
};

Hard 1100 StringDecryption

ながーいDP.

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair

#define MOD (1000000009LL)

long long dp[600][10][2];

class StringDecryption {
public:
    int decrypt(vector <string> code) {
        memset(dp, 0, sizeof(dp));
        string s(accumulate(code.begin(), code.end(), string()));
        int n = s.size();
        for(int i=n-2; i>=0; i--) if(s[i]!='0') {
            if(i==0 || s[i-1]!=s[n-1]) {
                if(s[n-1]=='0' || (i==n-2 && s[i]=='1')) dp[i][s[n-1]-'0'][1]=1;
                else dp[i][s[n-1]-'0'][0]=1;
            }
            for(int j=i+2; j<n-1; j++) if(i==0 || s[i-1]!=s[j-1]) {
                // a->integer, b->digit; sequence of `a` copies of `b`
                long long a=0;
                for(int k=i; k<j-1; k++) a=(a*10+s[k]-'0')%MOD;
                int b=s[j-1]-'0';
                // don't choose a digit from this sequence
                if(b>0) rep(k, 10) dp[i][k][0]=(dp[i][k][0]+dp[j][k][0]+dp[j][k][1])%MOD;
                else rep(k, 10) dp[i][k][1]=(dp[i][k][1]+dp[j][k][0]+dp[j][k][1])%MOD;
                // choose one digit
                if(b>0 && (j>i+2 || s[i]>'1')) {
                    // choose first
                    rep(k, 10) if(b!=k) dp[i][b][1]=(dp[i][b][1]+dp[j][k][0]+dp[j][k][1])%MOD;
                    // choose last
                    rep(k, 10) if(b!=k) dp[i][b][0]=(dp[i][b][0]+dp[j][k][0])%MOD;
                    // choose 2nd...n-1th
                    long long a2=(a-2+MOD)%MOD;
                    rep(k, 10) if(b!=k) dp[i][b][0]=(dp[i][b][0]+(dp[j][k][0]+dp[j][k][1])*a2)%MOD;
                }
                else {
                    // choose last
                    rep(k, 10) if(b!=k) dp[i][b][1]=(dp[i][b][1]+dp[j][k][0])%MOD;
                }
            }
        }
        long long ans=0;
        rep(i, 10) ans=(ans+dp[0][i][0])%MOD;
        return ans%MOD;
    }
};