hogecoder

tsutaj 競技プログラミングの記録

TopCoder SRM 729 Div2 Hard: RareItems

TopCoder

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

N 個のアイテムが出るくじがある。 i 番目のアイテムが出る頻度は f_i である (すなわち、 i 番目が出る確率は \frac{f_i}{\sum_{k=1}^{N} f_k} )。 N 個すべてのアイテムを出すまでに必要な、くじを引く回数の期待値を求めよ。

解説

このスライド の pp.36-40 を参照してください (雑)

確率と期待値について結構頑張ってまとめたスライドなのでほかも参考になれば嬉しいです。

ちなみに、 RareItems の類題として、 AtCoder の ソーシャルゲーム があります (くじが複数あるだけでほぼ同じ問題)

ソースコード

class RareItems {
    public:
    double expectedPurchases(vector<int> frequency) {
        int N = frequency.size();
        // すべてのアイテムの頻度の和 (全事象)
        int sum = accumulate(frequency.begin(), frequency.end(), 0);

        // dp[S] := 既に得たアイテムの集合が S であるとき、
        //          S からフルコンプするまでに必要な回数の期待値
        vector<double> dp(1<<N, 0.0);
        for(int bit=(1<<N)-1; bit>=0; bit--) {
            // 既に得ているアイテムの頻度和
            int already_get = 0;
            for(int i=0; i<N; i++) {
                if(bit >> i & 1) already_get += frequency[i];
            }

            // 未取得のアイテムの頻度和
            int sum_part = sum - already_get;

            if(sum_part) {
                // 未取得のアイテムが出るまで引く回数の期待値
                double exp_num = 1.0 * sum / sum_part;

                // 未取得のアイテムを何かひとつ引く → 集合を更新
                for(int i=0; i<N; i++) {
                    if(!(bit >> i & 1)) {
                        // 未取得のアイテムの集合が決定しているとき、
                        // i 番目のアイテムを引く確率 (条件付き確率)
                        double prob = 1.0 * frequency[i] / sum_part;
                        int nbit = bit | (1 << i);
                        dp[bit] += (dp[nbit] + exp_num) * prob;
                    }
                }
            }
        }
        return dp[0];
    }
};

TopCoder SRM 729 Div1 Easy: MagicNumberThree

TopCoder

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

数字のみからなる、 N \ \ (1 \leq N \leq 50) 文字の文字列が与えられる。この文字列の (連続とは限らない) 部分列であって、それを数字に直したときに 3 の倍数になるものの総数を、 1,000,000,007 で割った余りを求めよ。

解説

典型 DP で解けます。leading zero の文字列も普通に数えてしまって良いらしいので罠らしい罠はありません。

注意することがあるとすれば、部分列なので前のインデックスの結果もそのまま伝搬することと、空文字列を答えとしてカウントしないように最後に 1 引くくらいですかね？

int dp[60][3];
class MagicNumberThree {
    public:
    int countSubsequences(string s) {
        int N = s.length();

        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for(int i=0; i<N; i++) {
            int val = s[i] - '0';
            for(int k=0; k<3; k++) {
                (dp[i+1][k] += dp[i][k]) %= MOD;
                (dp[i+1][(k+val)%3] += dp[i][k]) %= MOD;
            }
        }
        return dp[N][0] - 1;
    }
};

TopCoder SRM 730 Div1 Easy (Div2 Hard): StonesOnATree

TopCoder

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

頂点に重み w_i がついている、 N 頂点からなる木がある。子よりも親の方がインデックスが小さく、重みについても子と同じか小さいことが保証される。

この木に石を置いたり、取り除いたりすることを考える。ある頂点に石が置ける条件とは、その頂点の子すべてに石が置かれていることである。取り除く際は、どこを取り除いてもよい。

ある状態に対して、石が置かれている頂点に対応する重みの和をコストとするとき、頂点 0 に石を置くために必要な最大コストの最小値を求めよ。

解説

ドワコン 2018 予選の D 問題 と設定と似ていますが、「重みが単調増加である」という点が異なります。

p_i かつ w \left[ i-1 \right] \leq w \left[ i \right] であることから、任意の頂点 v の重みについて、その子の重みと等しいか小さくなります。この制約により、ある頂点 v に対して、「その子 c_1 に石が置けるように操作し、それが終わってから別の子 c_2 に石が置けるように操作する」ことが最適になります。 c_1 に対して動かしている途中に c_2 に対して動かす必要がないということです。

よって、 \mathrm{dp} \left[ i \right] := 頂点 i に石を置くために必要な最大コストの最小値 とし、これを葉から根の方向に更新すれば良いです。

Div1 Easy では子の数は高々 2 なので、場合分けします。

子の数が 0 である場合は、葉なので明らかに w_i が入ります。

1 である場合は、自分の重みとその子の重みの和と、子に石を置くために必要なコストの \max です。

2 である場合について考えます。説明のため子である頂点を u, v とします。このとき、子に石を置く順番は u \rightarrow v または v \rightarrow u のどちらかです。このうち、コストが小さくなる方を選択すれば良いです。

Div2 Hard では二分木とは限らないので、もう少し考えます。

頂点 v の子を p_1, p_2, \dots, p_k とします。とりあえず、 p_1, p_2, \dots, p_k の順番に石を置き、それから v に石を置くことにしましょう。

p_1 を置くまでのコストは、 DP で計算している値そのものなので、 \mathrm{dp} \left[ p_1 \right] です。

p_2 を置くまでのコストは、既に p_1 が置かれているため \mathrm{w} \left[ p_1 \right] + \mathrm{dp} \left[ p_2 \right] になります。

このように、石を置くのが k 番目となる子 p_k について、そのコストは \mathrm{w} \left[ p_1 \right] + \dots + \mathrm{w} \left[ p_{k-1} \right] + \mathrm{dp} \left[ p_k \right] となり、あとは適切に石を置く順番を決めることでコストを最小化しようということになります。

ここで、任意の v について、 \mathrm{w} \left[ v \right] \leq \mathrm{dp} \left[ v \right] であることを利用します (これは v を置くために必ず \mathrm{w} \left[ v \right] かかることを考慮すれば明らかです)。 \mathrm{w} \left[ p_1 \right] + \dots + \mathrm{w} \left[ p_{k-1} \right] \leq \mathrm{w} \left[ p_1 \right] + \dots + \mathrm{dp} \left[ p_{k-1} \right] ですから、 \mathrm{dp} の値と \mathrm{w} の値の差分が大きい物から先に配置していけば、最終的なコストは小さくなります。よって、このルールに従って子をソートすれば解けます。

最後に、子の重みの総和と自分自身の重みの和を考慮し忘れないように気をつけましょう。

ソースコード

Div1

class StonesOnATree {
    public:
    int minStones(vector<int> p, vector<int> w) {
        int N = w.size();
        vector< vector<int> > children(N);
        for(int i=0; i<N-1; i++) {
            children[ p[i] ].push_back(i+1);
        }

        vector<int> dp(N);
        for(int i=N-1; i>=0; i--) {
            int sz = children[i].size();
            if(sz == 0) {
                dp[i] = w[i];
            }
            if(sz == 1) {
                int u = children[i][0];
                dp[i] = max(dp[u], w[i] + w[u]);
            }
            if(sz == 2) {
                int u = children[i][0], v = children[i][1];
                // u -> v
                int vl = max(dp[u], w[u] + dp[v]);
                // v -> u
                int vr = max(dp[v], w[v] + dp[u]);
                dp[i] = max(w[i] + w[u] + w[v], min(vl, vr));
            }
        }
        return dp[0];
    }
};

Div2

class StonesOnATreeDiv2 {
    public:
    int minStones(vector<int> p, vector<int> w) {
        int N = w.size();
        vector< vector<int> > children(N);
        for(int i=0; i<N-1; i++) {
            children[ p[i] ].push_back(i+1);
        }

        vector<int> dp(N);
        for(int i=N-1; i>=0; i--) {
            sort(children[i].begin(), children[i].end(), [&](int l, int r) {
                return dp[l] - w[l] > dp[r] - w[r];
            });

            int sum_weight = 0;
            for(size_t k=0; k<children[i].size(); k++) {
                int u = children[i][k];
                dp[i] = max(dp[i], sum_weight + dp[u]);
                sum_weight += w[u];
            }
            sum_weight += w[i];
            dp[i] = max(dp[i], sum_weight);
        }
        return dp[0];
    }
};