Algoogle

Algorithm for Programming Contest

SRM 618 Div1

Category: TopCoder Tag: dp

Easy


Family
親同士に辺を張って交互に2色に塗るだけ. 矛盾したらImpossible.

コード


(618div1easy.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
vector<int> edge[128];
int col[128];
class Family {
public:
    int N;
    string pos = "Possible";
    string imp = "Impossible";

    bool dfs(int p, int g){
        if(col[p] >= 0) return col[p] == g;
        col[p] = g;
        rep(i, edge[p].size())
            if(!dfs(edge[p][i], 1-g)) return 0;
        return 1;
    }

    string isFamily( vector <int> p1, vector <int> p2 ) {
        N = p1.size();
        rep(i,N) edge[i].clear();
        memset(col, -1, sizeof(col));
        rep(i,N){
            if(p1[i] >= 0){
                edge[p2[i]].pb(p1[i]);
                edge[p1[i]].pb(p2[i]);
            }
        }
        rep(i,N)if(col[i] < 0)
            if(!dfs(i, 0)) return imp;
        return pos;
    }
};

Medium


LongWordsDiv1
使う文字を左からA, B, …とする. 答えは最後に並べ替えた分かければ良い.
このとき作られる文字列は2パターンある.
AaAとAaAbAというパターン(a, bはA以外で作られた文字列).
1つ目は明らかにBC..CBにAをつけただけなので使う文字が1つ分少ない場合の数.
2つ目もa, bで使われる文字数の組み合わせを全て回してやればよい.

コード


(618div1medium.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define int long long
const int mod = 1e9+7;
int dp[5010];
class LongWordsDiv1 {
public:
    signed count( signed n ) {
        memset(dp, 0, sizeof(dp));
        dp[1] = dp[2] = 1;
        repi(i,3,n+1){
            dp[i] = dp[i-1];
            repi(j,1,i-1)
                dp[i] = (dp[i]+dp[j]*dp[i-j-1]%mod)%mod;
        }
        int ans = dp[n];
        repi(i,1,n+1) ans = (ans*i)%mod;
        return ans;
    }
};
#undef int

Comments