2018-03-05

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

TopCoder 数学

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

長さ $N+M$ の順列 $p$ であって、先頭 $M$ 要素について $p_i \neq i$ が成立するようなものの総数を求めよ。

解説

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

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

$p_i = i$ を満たす要素が $k$ 個ある順列の総数を考えます。これは $f(M) :=$ 先頭 $M$ 要素について $p_i \neq i$ を満たす順列の総数と定義するとき、 ${}_{M} C_{k} \times f(M-k)$ と計算できます ( $p_i = i$ となる要素の場所が combination で計算でき、それを除いた状態を考えると再帰的に計算できる)。

f:id:tsutaj:20180305160642p:plain

よって、この問題の答えは、順列が $(N+M)!$ 通りある中から、「 $p_i = i$ を満たす要素が $k \ \ (1 \leq k \leq M)$ 個ある」場合を引いたものであるため、

$f(M) = (N+M)! - \sum_{k=1}^{M} {}_{M} C_{k} \times f(M-k)$

と求められます。これは $O(M^{2})$ で動きます。

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

$1$ 番目の要素が $x \ \ (1+M \leq x \leq N+M)$ である (これは $N$ 通りあり、 $x$ 番目の要素には何が来ても良いため、残りの数の並べ方は $f(M-1)$ に等しい)
$1$ 番目の要素が $x \ \ (1 \leq x \leq M)$ であって、 $x$ 番目の要素が $1$ (これは $M-1$ 通りあり、 $1$ 番目と $x$ 番目の要素についてはもう考慮する必要がないので、残りの数の並べ方は $f(M-2)$ に等しい)
$1$ 番目の要素が $x \ \ (1 \leq x \leq M)$ であって、 $x$ 番目の要素が $1$ (これは $M-1$ 通りあり、残りの数の並べ方は $f(M-1)$ に等しい)

以上を踏まえると、 $f(M) = (N+M-1)f(M-1) + (M-1)f(M-2)$ となり、 $O(M)$ で求められます。

ソースコード

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

2018-03-04

TopCoder SRM 718 Div2 Hard: ChainCity

TopCoder

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

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

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

解説

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

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

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

ソースコード

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

2018-03-04

TopCoder SRM 718 Div1 Easy (Div2 Med): InterleavingParenthesis

TopCoder 文字列動的計画法

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

括弧列 $S_1$ と $S_2$ が与えられる。

$S_1$ に $S_2$ の各文字を、 $S_2$ の文字間の相対位置関係を変えずに挿入することを考える。このとき、 valid な括弧列になるパターンは何通りあるか？ただし、文字として同じであっても、もともと $S_1$ の文字であったか $S_2$ の文字であったかは区別される。

解説

まず、ここでいう valid な括弧列 $S$ とは、'(' を $+1$ と、 ')' を $-1$ と見たとき、以下と同値です。

全要素の総和が $0$
先頭からの累積和が一度も負にならない

したがって、 $S_1$ の累積和と $S_2$ の累積和の和を取った時に $0$ でなければ、どう並べても valid な括弧列は作れません。

さて、 $S_1$ の $i$ 文字目、 $S_2$ の $j$ 文字目までを既に使用したとしましょう。この後の文字を適切に並べることで valid な括弧列を作れるかどうかの判定は、累積和が非負であるかどうかで可能です。

先ほどの状態から $1$ つ進んだ状態、すなわち $S_1$ または $S_2$ から新たに $1$ 文字使うことを考えましょう。ここでの valid な括弧列判定も、やはり累積和で行えます。

ここまで来ると $\mathrm{dp} \left[ i \right] \left[ j \right] :=$ $S_1$ の $i$ 文字目、 $S_2$ の $j$ 文字目までを使用したときの valid になる可能性のある括弧列の総数という DP が構成でき、 $O(|S_1| |S_2|)$ で解くことができます。

ソースコード

class InterleavingParenthesis {
    public:
    int sum1[2510], sum2[2510];
    int dp[2510][2510];
    int d1[2] = {1, 0};
    int d2[2] = {0, 1};
    int countWays(string s1, string s2) {
        int N = s1.length(), M = s2.length();
        memset(sum1, 0, sizeof(sum1));
        memset(sum2, 0, sizeof(sum2));
        for(int i=0; i<N; i++) {
            sum1[i+1] = sum1[i] + (s1[i] == '(' ? 1 : -1);
        }
        for(int i=0; i<M; i++) {
            sum2[i+1] = sum2[i] + (s2[i] == '(' ? 1 : -1);
        }
        if(sum1[N] + sum2[M] != 0) return 0;

        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for(int i=0; i<=N; i++) {
            for(int j=0; j<=M; j++) {
                int cur_sum = sum1[i] + sum2[j];
                if(cur_sum < 0) continue;

                for(int k=0; k<2; k++) {
                    int ni = i + d1[k], nj = j + d2[k];
                    if(ni > N || nj > M) continue;
                    int nxt_sum = sum1[ni] + sum2[nj];
                    if(nxt_sum < 0) continue;
                    (dp[ni][nj] += dp[i][j]) %= MOD;
                }
            }
        }
        return dp[N][M];
    }
};