CS Academy Ball Sampling

リンク : https://csacademy.com/contest/archive/task/ball-sampling/

問題概要

N色のボールがあり、箱にそれぞれA_i個入っている。同様に確からしいとき、すべての色のボールを一回以上取り出す期待値を求めよ。

解説

いわゆる、コンプリート問題と言われる、期待値と言えばの典型である。tsutajさんの下のスライドにとてもよくまとめられている。
http://compro.tsutajiro.com/archive/180220_probability_dp.pdf
dp[mask]を1回でも取った色の情報をmaskとして、maskから全色集めるまでの期待値とする。最終的な答えはdp[0]となる。

LL n, a[1100], sum;
double dp[1 << 20];
int main() {
    cin >> n;
    rep(i, n) {
        cin >> a[i];
        sum += a[i];
    }
    Rrep(mask, (1LL << n)) {
        LL cur = 0;
        rep(i, n)if ((mask&(1LL << i)) == 0)cur += a[i];
        double p = sum;
        p /= cur;
        rep(i, n) {
            if ((mask&(1LL << i)) == 0) {
                double q = a[i];
                q /= cur;
                dp[mask] += (dp[mask | (1LL << i)] + p) * q;
            }
        }
    }
    printf("%.15f\n", dp[0]);
    return 0;
}

CS Academy Amusement Park

リンク : https://csacademy.com/contest/archive/task/amusement-park/statement/

問題概要

N*Mの行列Aが与えられる。このA[i][j]は座標(i,j)からA[i][j]の確率で座標(i,j+1)に進み、それ以外は座標(i+1,j+1)に進む。このとき、iがNになるときの移動回数の期待値を求めよ。

解説

期待値周りの計算がガッチガチの数学なので、公式の解説を読んだほうがわかりやすいかも。dp[i][j]を今の座標からNになるまでの期待値とする。
dp[0][N]=dp[0][N-1]×A[0][N-1]
dp[0][N-1]=dp[0][N-2]×A[0][N-2]......
dp[0][1]=dp[0][0]×A[0][0]
dp[0][0]=dp[0][N]×A[0][N]
となり、円のように循環になる。なので、dp[0][0]の値が求められると、すべて求められることになる。また、x=dp[0][0]とおくと、後ろから求めることにより、x=a+bxの形になるため、xが求められる。
次にdpiについて考えると、dp[i][N]=dp[i][N-1]×A[i][N-1]+dp[i-1][N-1]×(1-A[i][N-1])......となり、これもまた先ほどと同じように求められる。

int T, A;
double a[1100][1100],dp[1100][1100];
int main() {
    cin >> T >> A;
    rep(i, T)rep(j, A) {
        cin >> a[i][j];
        a[i][j] /= 100;
    }
    for (int i = 0; i<T; i++) {
        double sum1 = 1, sum2 = 1 + (i - 1 >= 0 ? dp[i - 1][0] * (1 - a[i][A - 1]) : 0);
        for (int j = A - 1; j >= 0; j--) {
            sum1 *= (a[i][j]);
            if (j != A - 1)sum2 = (1 + sum2 * (a[i][j]) + (i-1>=0?dp[i - 1][(j+1)%A] * (1 - a[i][j]):0));
        }
        dp[i][0] = sum2 / (1-sum1);
        for (int j = A-1; j >=0; j--) {
            dp[i][j] = 1.0 + dp[i][(j+1)%A] * a[i][j] + (i - 1 >= 0 ? dp[i - 1][(j + 1) % A] * (1 - a[i][j]) : 0);
        }
    }
    printf("%.15f\n",dp[T-1][0]);
    return 0;
}

CS Academy City Attractions

リンク : https://csacademy.com/contest/archive/task/city-attractions/statement/

問題概要

N頂点の木が存在する。それぞれの頂点に美しさA[i]として入力される。d(x,y):=頂点xと頂点yの距離とする。頂点xにいるとき、次に進む場所はA[y]-d(x,y)が最大になる都市である。K回進んだとき、最後の頂点はいくつか。

解説

すぐに全方位木dpっぽいなとは思ったが、MLEがつらすぎた... 全方位木dpとは簡単に説明すると、全頂点を根として一回探索したいときにO(N²)ではなく、O(N)でできる考え方である。一度全方位木dpをして、頂点iにいるときに次に進む場所を計算しておく。これができれば、あとは頂点1から順番に見ていってサイクルが必ず存在するためKをサイクルの大きさで割った余りにして、また前から見ていけばO(N)で答えを求めることができる。

LL n, k, a[300010], h[300010];
vector<LL>g[300010];
Pll nex[300010], dp[300010];
bool f[300010];
void cmp(Pll &x,Pll y) {
    if (x.fir < y.fir||(x.fir==y.fir&&x.sec>y.sec))
        x = y;
}
void dfs1(LL cur, LL par) {
    nex[cur] = Pll{ -INF / 2,-1 };
    rep(i, g[cur].size()) {
        LL v = g[cur][i];
        if (v == par)continue;
        dfs1(v, cur);
        cmp(nex[cur], { nex[v].fir - 1,nex[v].sec });
        cmp(nex[cur], { a[v] - 1,v });
    }
}
void dfs2(LL cur, LL par) {
    if (par != -1) {
        cmp(dp[cur], { dp[par].fir - 1, dp[par].sec});
        cmp(dp[cur], Pll{ a[par] - 1,par });
    }
    Pll mx = Pll{ -INF / 2,-1 };
    rep(i, g[cur].size()) {
        LL v = g[cur][i];
        if (v == par)continue;
        cmp(dp[v], { mx.fir - 2,mx.sec });
        cmp(mx, nex[v]);
        cmp(mx, { a[v],v });
    }
    reverse(g[cur].begin(), g[cur].end());
    mx = Pll{ -INF / 2,-1 };
    rep(i, g[cur].size()) {
        LL v = g[cur][i];
        if (v == par)continue;
        cmp(dp[v], { mx.fir - 2,mx.sec});
        cmp(mx, nex[v]);
        cmp(mx, { a[v],v });
    }
    rep(i, g[cur].size()) {
        LL v = g[cur][i];
        if (par == v)continue;
        dfs2(v, cur);
    }
    cmp(dp[cur], nex[cur]);
    h[cur] = dp[cur].sec;
}
int main() {
    cin >> n>>k;
    rep(i, n) {
        cin >> a[i];
    }
    rep(i, n - 1) {
        LL x, y;
        cin >> x >> y;
        x--, y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    rep(i, n)dp[i] = Pll{ -INF / 2,-1 };
    dfs1(0, - 1);
    dfs2(0, -1);
    LL to = 0;
    while (f[to]==0) {
        f[to] = 1;
        to = h[to];
        k--;
        if (k == 0) {
            cout << to + 1 << endl;
            return 0;
        }
    }
    rep(i, n)f[i] = 0;
    LL cnt = 0;
    while (f[to] == 0) {
        f[to] = 1;
        to = h[to];
        cnt++;
    }
    k %= cnt;
    while (k > 0)to = h[to], k--;
    cout << to + 1 << endl;
    return 0;
}

CS Academy Subarray Medians

リンク : https://csacademy.com/contest/archive/task/subarray-medians/

問題概要

長さNの数列が与えられる。(1<=i<=j<=N かつ j-i=0 mod2)のすべてのi,jに関して[i,j]の中央値をmとしたとき、ijmの総和を求めよ。

解説

最初、iを決めて、前から順にBIT上のa[j]に1を足して、二部探索してO(N² logn)で求めたら、TLEしてしまった。ここで違うアプローチを考える。すべてのi,jの中央値を考えるのではなく、iがmとして取られるときの総和を求めることにする(割とこの考えは使う)。i<=jのとき、[i,j]に(a[i]より大きい個数)-(a[i]より小さい個数)をdifとする。d[dif]+=jをする。次にj<=iを見た時に、[j,i]に(a[i]より大きい個数)-(a[i]より小さい個数)をdifとすると、d[-dif]ja[i]をとることによってj番目から始まる区間で、中央値がi番目となるときをすべて考えることができる。

LL n, ans, a[11000], d[11000];
int main() {
    cin >> n;
    rep(i, n) {
        cin >> a[i];
    }
    rep(i, n) {
        rep(j, 11000)d[j] = 0;
        LL dif = 5000;
        for (int j = i; j >=0; j--) {
            if (a[i] > a[j])dif++;
            else dif--;
            if (dif <= 10000 && dif >= 0)d[dif] += (j + 1);
        }
        dif = 5000;
        for (int j = i; j < n; j++) {
            if (a[i] >= a[j])dif--;
            else dif++; 
            if (dif <= 10000 && dif >= 0)ans += a[i] * d[dif] * (j + 1);
        }
    }
    cout << ans << endl;
    return 0;
}

CS Academy Maxor

リンク : https://csacademy.com/contest/archive/task/maxor/statement/

問題概要

N個の数字が与えられ、任意の二つの数字をorで計算したときの最大値とこの最大値となる通り数を求めよ。

解説

これもまた高速ゼータ変換...dp1[i]をiを部分集合としてもつ数字の個数とする。これは高速ゼータ変換で簡単に求められる。次に、dp2[i]をiとNこの数字それぞれに&をしたときの最大値とする。この問題の最大値の答えをmとすると、m=max{ {i=1,2,...N}{A[i] or dp2[~A[i]]} }となる。これを求めるほうが、通り数を求めるより難しかった。dp1[i]の数字が正のときはdp2[i]=iとなる。それ以外の場合はdp2[i]=max{ {j=0,1..17}{if(i&(1<<j))dp2[i xor (1<<j)]} }となる。

LL n, ans, dp1[1 << 20], dp2[1 << 20], a[110000];
int main() {
    cin >> n;
    rep(i, n) {
        cin >> a[i];
        dp1[a[i]] += 1;
        dp2[a[i]] = a[i];
    }
    rep(i, 20) rep(b, 1LL << 20)
        if (0 == (b & (1LL << i))) {
            dp1[b] += dp1[b | (1LL << i)];
        }
    rep(b, 1LL << 20)if (dp1[b] > 0)dp2[b] = b;
    Rrep(i, 20) rep(b, 1LL << 20)
        if ((b & (1LL << i))) {
            dp2[b] = max(dp2[b], dp2[b ^ (1LL << i)]);
        }

    LL mx = 0;
    rep(i, n) {
        mx = max(mx, a[i] | dp2[((1LL << 20) - 1)^ a[i] ]);
    }
    rep(i, n) {
        if (mx == a[i]) {
            ans += dp1[0] - 1;
        }
        else if ((mx&a[i]) == a[i]) {
            ans += dp1[mx - a[i]];
        }
    }
    cout <<mx<<" "<< ans/2 << endl;
    return 0;
}

CS Academy Max Score Tree

リンク : https://csacademy.com/contest/archive/task/max-score-tree/statement/

問題概要

N頂点の木とScoreiが与えられる。木のスコアは木に含まれる頂点vが持つ辺の数をEdge[v]とすると、この木のスコアはΣScore[Edge[v]]となる。入力で与えられた木の部分木が満たす最大のスコアを求めよ。

解説

dp[i]を自分の親を部分木として持つ場合の最大のスコアとする。持たない場合も別で計算しておくことも考えておく。頂点vに関して考えるとする。この頂点が持つ辺の集合をEとする。Eのそれぞれに関して、dp[e}(e∈E)をsortして上から貪欲にとって行くことを考える。上からi個足したものをsum[i]とすると、dp[v]=max{sum[i]+Score[i+1]}となる。もし親を持たないときはmax{sum[i]+Score[i]}となる。

LL n, score[110000], dp[110000], ans = -INF;
vector<vector<LL>>g,rvec;
LL func(int cur ,int par) {
    LL ret = score[1], sum = 0;
    if (dp[cur] != -INF)return dp[cur];
    vector<LL>d;
    rep(i, g[cur].size()) {
        LL v = g[cur][i];
        if (v == par)continue;
        func(v, cur);
        d.push_back(dp[v]);
    }
    sort(d.begin(), d.end(), [](LL x, LL y) {return x > y; });
    rep(i, d.size()) {
        sum += d[i];
        ret = max(ret, sum + score[i + 2]);
        ans = max(ans, sum + score[i + 1]);
    }
    return dp[cur] = ret;
}
int main() {
    cin >> n;
    rep(i, n)cin >> score[i];
    g.resize(n);
    rep(i, n - 1) {
        LL x, y;
        cin >> x >> y;
        x--, y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    rep(i, n)dp[i] = -INF;
    func(0, -1);
    cout << max(score[0],ans) << endl;
    return 0;
}

CS Academy Distinct Palindromes

リンク : https://csacademy.com/contest/archive/task/distinct-palindromes/statement/

問題概要

文字列が与えられる。この文字列の部分文字列であり、回文であるのは何種類か求めよ。

解説

文字列をSとし、i番目の文字をS[i]とする。dp[l][r]をS[l]=S[r]=σであるときに、必ずlとrを回文に含む[l~r]間の回文の種類数とする。(l~r)の間に文字cが二つ以上存在するとき、(l~r)間にありlから最も近い文字cをc_l番目、rから最も近い文字cをc_r番目とする。σc...cσと取ることになる。dp[l][r]+=dp[c_l][c_r]となる。またこのσのときの間に一つしか文字がないときの場合は、a~zのそれぞれの文字について(l~r)間に存在すればdp[l][r]+=1する。最後にσσのみも考慮してdp[l][r]+=1する。これですべての遷移が終わった。実装する際にa~z以外の文字を番兵にすることで実装が楽になる。 下の図が具体例となる。$を番兵とする。答えに∅を回文として含んでしまうため-1をする。

これ典型なんですか？

kmjpさんのコードを参考にしました。

string str;
LL n;
LL dp[1010][1010], r[1010][30], l[1010][30];
LL func(int L, int R) {
    if (dp[L][R] != -1)return dp[L][R];
    LL ret = 1;
    rep(i, 26)if (r[L][i]<R&&l[R][i]>L) {
        ret++;
        if (r[L][i] < l[R][i])ret += func(r[L][i], l[R][i]);
        ret %= MOD;
    }
    return dp[L][R] = ret;
}
int main() {
    cin >> str;
    str = (char)('a' + 26) + str + (char)('a' + 26);
    n = str.size();
    rep(i, n + 1)rep(j, n + 1)dp[i][j] = -1;
    rep(i, n)str[i] -= 'a';
    rep(i, 30)r[n - 1][i] = n, l[0][i] = -1;
    for (int i = n - 2; i >= 0; i--) {
        rep(j, 27) {
            if (str[i + 1] == j)r[i][j] = i + 1;
            else r[i][j] = r[i + 1][j];
        }
    }
    for (int i = 1; i<n; i++) {
        rep(j, 27) {
            if (str[i - 1] == j)l[i][j] = i - 1;
            else l[i][j] = l[i - 1][j];
        }
    }
    cout << (func(0, n - 1)-1+MOD)%MOD << endl;
    return 0;
}