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;
    }
};

TopCoder SRM 718 Div2 Hard: ChainCity

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

次元座標上に点が 個並んでいる。ここに新たに点を 個まで追加することを考える。

点 から まで移動するときにかかる時間は、通常は 動くごとに 秒かかるが、新たに追加した点どうしは瞬時に移動でき、時間はかからない。このとき、任意の 点間の移動時間の最大値を最小化せよ。

解説

最大値の最小化なので、二分探索がしたい気持ちになります。この場合、どのように二分探索できるでしょうか？

最小値を にできるかを判定することを考えます。この判定は、長さ の区間を 個以下用いて、元からあった頂点すべてを被覆できるかどうかを見る ことで可能です。

なぜこれでうまくいくのでしょうか？まず、ひとつの区間に含まれている点どうしの移動時間は当然 以下なので条件を満たしています。また、異なる区間に含まれている点同士であったとしても、各区間の中点に相当するところに新たに点を (瞬間移動可能な点を) 置くことによって、最大で の移動時間になり、条件を満たしています。この区間の長さを短くしていくと、条件を満たすためにはより多くの区間が必要になるという単調性があり、この条件で二分探索が可能です。

ソースコード

class ChainCity {
    public:
    // 長さ x の区間を k 個まで使って全てを被覆できるか
    bool d(ll x, ll k, vector<int> dist) {
        ll ub = x, pos = 0, cnt = 1;
        for(size_t i=0; i<dist.size(); i++) {
            pos += dist[i];
            if(pos > ub) {
                ub = pos + x;
                cnt++;
            }
        }
        return cnt <= k;
    }
    int findMin(vector<int> dist, int k) {
        ll lb = -1, ub = INF;
        while(ub - lb > 1) {
            ll mid = (lb + ub) / 2;
            (d(mid, k, dist) ? ub : lb) = mid;
        }
        return ub;
    }
};