TopCoder SRM 716 Div1 Easy: ConstructLCS

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

以下の条件を全て満たすような '0' と '1' のみからなる文字列 を構成せよ。

• と の最長共通部分列 (LCS) が
• と の LCS が
• と の LCS が

解説

を仮定すると、次のような文字列を構成すれば良いことが分かります。

• 文字列 → 文字の '0'
• 文字列 → 文字の '0' と、 文字の '1'
• 文字列 → 文字の '1' と、 文字の '0'

なぜ大小関係が必要かというと、これがないと色々と不都合が生じる可能性があるからです ( と の LCS について、 のほうではなく の方が採用されるかも、などなど)

しかし実際にはこの仮定はないため、どうするかと言うと、上と同じ方法で文字列を つ作り、そのうちどれを に、どれを に、どれを に当てはめるかを全て試し、その都度 LCS を取ります。どれかは必ず条件を満たしているので、これで解くことが出来ます。

ソースコード

class ConstructLCS {
    public:
    int calclcs(string a, string b) {
        int dp[1010][1010] = {};
        int n = a.length(), m = b.length();
        rep(i,0,n) rep(j,0,m) {
            if(a[i] == b[j]) dp[i+1][j+1] = dp[i][j] + 1;
            else dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
        }
        return dp[n][m];
    }

    string construct(int ab, int bc, int ca) {
        vector<int> ns = {ab, bc, ca};
        sort(ns.begin(), ns.end(), greater<int>());

        vector<string> strs(3);
        strs[0] = string(ns[0], '1');
        strs[1] = string(ns[0], '1') + string(ns[1], '0');
        strs[2] = string(ns[1], '0') + string(ns[2], '1');
        vector<int> perm = {0, 1, 2};
        do {
            string ra = strs[perm[0]], rb = strs[perm[1]], rc = strs[perm[2]];
            int nab = calclcs(ra, rb);
            int nbc = calclcs(rb, rc);
            int nca = calclcs(rc, ra);
            if(nab == ab && nbc == bc && nca == ca) {
                return ra + " " + rb + " " + rc;
            }
        }while(next_permutation(perm.begin(), perm.end()));
        return "";
    }
};

TopCoder SRM 716 Div1 Med (Div2 Hard): JumpDistancesOnTree

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

頂点からなる木がある。頂点 を起点として、いくつかの頂点に移動することを考える。集合 が与えられるので、頂点 の順に移動したときの隣り合う要素どうしの距離 の中に の要素が全て含まれるような移動方法があるかを判定せよ。

解説

頂点 から行ける場所であって、頂点間の距離が の元であるような要素を管理したいです。これをするにはどうすればよいでしょうか？

に含まれている移動距離であるような頂点間が何であるかを把握します。これは全点対の距離を調べることで可能です。そして、その頂点間にのみ辺を貼ったグラフを新たに考え、 Union Find で連結成分を把握します。頂点 が属している連結成分に の元が全てあればよいので、それを判定すれば解くことが出来ます。

Div1 では制約が大きいだけなのですが、LCA 使った全点対を書いたら を通してくれないようで悲しい・・・もう少し考えます・・・

(追記) 木なら普通に dfs なりをやって全点対 だから LCA とかいらなかったですね (アホすぎる)

ソースコード

Div1 (UnionFind 省略, Div2 でもこれで通るはず)

class JumpDistancesOnTree {
    public:
    int dist[MAX_N + 10][MAX_N + 10];
    int assigned[MAX_N + 10];

    void dfs(Graph<int> &G, int cur, int orig, int par=-1, int d=0) {
        dist[cur][orig] = dist[orig][cur] = d;
        for(auto e : G[cur]) {
            if(e.to == par) continue;
            dfs(G, e.to, orig, cur, d+e.cost);
        }
    }

    string isPossible(vector<int> p, vector<int> S) {
        memset(assigned, false, sizeof(assigned));
        int N = p.size() + 1;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                dist[i][j] = (i == j ? 0 : INF);
            }
        }

        for(auto x : S) {
            assigned[x] = true;
        }

        Graph<int> G(N);
        for(int i=0; i<N-1; i++) {
            int u = i+1, v = p[i];
            G[u].push_back(Edge<int>(v, 1));
            G[v].push_back(Edge<int>(u, 1));
        }
        for(int i=0; i<N; i++) {
            dfs(G, i, i);
        }

        UnionFind uf;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(assigned[ dist[i][j] ]) {
                    uf.unite(i, j);
                }
            }
        }

        int ans = 0, root = uf.find(0);
        vector<int> cnt(MAX_N);
        for(int i=0; i<N; i++) {
            int idx = uf.find(i);
            if(idx != root) continue;
            for(int j=0; j<N; j++) {
                if(assigned[ dist[i][j] ]) {
                    if(!cnt[dist[i][j]]) ans++;
                    cnt[dist[i][j]] = true;
                }
            }
        }

        bool ok = (ans == (int)S.size());
        return (ok ? "Possible" : "Impossible");
    }
};

TopCoder SRM 717 Div 2 Hard (Div1 Med): DerangementsStrikeBack

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

長さ の順列 であって、先頭 要素について が成立するようなものの総数を求めよ。

解説

Div2 では制約が小さいため、以下のように解くことができます。

「先頭 要素について である」事象の余事象を考えます。つまり、 を満たす要素が少なくとも つある状況です。

を満たす要素が 個ある順列の総数を考えます。これは 先頭 要素について を満たす順列の総数 と定義するとき、 と計算できます ( となる要素の場所が combination で計算でき、それを除いた状態を考えると再帰的に計算できる)。

よって、この問題の答えは、順列が 通りある中から、 「 を満たす要素が 個ある」場合を引いたものであるため、

と求められます。これは で動きます。

Div1 では であるため、まだ足りません。ここで、 AtCoder Regular Contest 009 C: 高橋君、24歳 - hogecoder と同じように、完全順列と同じような考察をすることにしましょう。 は 番目の要素に関して次のような場合分けをすることで求められます。

• 番目の要素が である (これは 通りあり、 番目の要素には何が来ても良いため、残りの数の並べ方は に等しい)
• 番目の要素が であって、 番目の要素が (これは 通りあり、 番目と 番目の要素についてはもう考慮する必要がないので、残りの数の並べ方は に等しい)
• 番目の要素が であって、 番目の要素が (これは 通りあり、残りの数の並べ方は に等しい)

以上を踏まえると、 となり、 で求められます。

ソースコード

Div2 (どうせ comb の配列を初期化しなくても動くだろうと思って出したら落ちたので、初期化は大事です)

class DerangementsDiv2 {
    public:
    ll comb[110][110];
    ll fact[110], dp[110];
    int count(int n, int m) {
        memset(comb, 0, sizeof(comb));
        fact[0] = comb[0][0] = 1;
        for(int i=1; i<=n+m; i++) {
            fact[i] = (fact[i-1] * i) % MOD;
            comb[i][0] = 1;
            for(int j=1; j<=i; j++) {
                comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
            }
        }

        for(int i=0; i<=m; i++) {
            dp[i] = fact[n+i];
            for(int k=1; k<=i; k++) {
                ll sub = (comb[i][k] * dp[i-k]) % MOD;
                dp[i] = (dp[i] - sub + MOD) % MOD;
            }
        }

        return dp[m];
    }
};

Div1

class DerangementsStrikeBack {
    public:
    ll dp[100010];
    int count(int n, int m) {
        dp[0] = 1, dp[1] = n;
        for(int i=2; i<=m; i++) {
            dp[i] = ((n+i-1) * dp[i-1] + (i-1) * dp[i-2]) % MOD;
        }

        ll ans = 0;
        for(int i=1; i<=m; i++) {
            ans ^= dp[i];
        }
        return ans;
    }
};