Educational Codeforces Round 69 D: Yet Another Subarray Problem

問題概要

原文 → Problem - D - Codeforces

長さ の整数列 と、パラメータ が与えられる。

数列内の連続する閉区間 について、そのコストは で表される。なお、空の区間に対するコストは である。

あり得る全ての区間を考慮した時のコストの最大値を求めよ。

解法

で割った切り上げ、というパートが存在しなければよくある問題で、最適な左端のみを覚えながら右端を ずつ伸ばしていけば良い (累積和を取って変形すると、左端に関しては累積和の が必要になる)。

しかし今回は切り上げがあるので少し工夫が必要。

インデックスを で考え、合同となるインデックスはまとめて管理しよう。 番目までインデックスを伸ばすときは における最適値が変わる可能性があり、直前の値を持ってくるか、それまで最適だったものをそのまま使うかの 通りを考慮する必要がある。

ソースコード

int main() {
    ll N, M, K; scanf("%lld%lld%lld", &N, &M, &K);
    vector<ll> A(N);
    for(int i=0; i<N; i++) scanf("%lld", &A[i]);
    vector<ll> S(N+1);
    for(int i=0; i<N; i++) S[i+1] = S[i] + A[i];

    ll ans = 0;
    vector<ll> opt(M, INF);
    for(int i=1; i<=N; i++) {
        opt[(i-1)%M] = min(opt[(i-1)%M] + K, S[i-1] + K);
        for(int k=0; k<M; k++) chmax(ans, S[i] - opt[k]);
    }
    printf("%lld\n", ans);
    return 0;
}

本番では が大きい場合しか解けなかった (右端を まで伸ばしたときに について何倍するか変化するのは高々 個なので、変化するところだけ愚直に更新していっても が 以上だと全体でも なので使えるはず)

小さいときにどうするかは全く思い浮かばなかったのでかなしい

Educational Codeforces Round 18 E: Colored Balls

問題概要

原文 → Problem - E - Codeforces

色のボールがあり、 番目の色で塗られたボールは 個ある。

これらのボールを以下の条件を全て満たすように箱に入れる。

• それぞれの箱について、箱の中にあるボールの色は 種類のみ
• 空箱が存在しない
• 箱に入っているボールの個数の最大値と最小値の差は高々

必要な箱の個数の最小値を求めよ。

解説

色目のボールを箱に入れることを考える。積を考えると、「箱の個数」または「箱に入れるボールの個数」のいずれかは 以下であることが分かる。なのでそれぞれについて問題を解けばよい。

箱の個数が定まっているときに、それぞれの箱に入れるボールの個数がどうなるべきかは割り算をするとわかる。(剰余が のときに注意)

あとは「箱に入れるボールの個数が 個または であるときに、条件を満たす入れ方が可能か？また可能な時の箱の数の最小値がいくらか？」を解ければ良いことになる。

実は、各 について最適な箱の数は であり、入れ方が可能かどうかの判定は を満たすかどうかで可能である。

上の条件を満たすと仮定すると が成立するが、これは「全ての箱に 個入れたと仮定した時の個数」と「全ての箱に 個入れたと仮定した時の個数」で を挟んでいることに相当している。

ソースコード

int main() {
    int N; scanf("%d", &N);
    vector<int> A(N);
    for(int i=0; i<N; i++) scanf("%d", &A[i]);

    ll ans = INF;
    {
        // 箱の個数について
        for(int x=1; x*x<=A[0]; x++) {
            int d = A[0] / x, m = A[0] % x;
            for(int k=d; k>=d-(m==0); k--) {
                int mi = k, ma = k+1;
                ll sum = 0;
                for(int i=0; i<N; i++) {
                    ll b = (A[i] + ma - 1) / ma;
                    if(mi * b <= A[i]) sum += b;
                    else sum = INF;
                }
                ans = min(ans, sum);
            }
        }
    }

    {
        // 箱に入れるボールの個数について (x か x+1)
        for(int x=1; x*x<=A[0]; x++) {
            int mi = x, ma = x+1;
            ll sum = 0;
            for(int i=0; i<N; i++) {
                ll b = (A[i] + ma - 1) / ma;
                if(mi * b <= A[i]) sum += b;
                else sum = INF;
            }
            ans = min(ans, sum);
        }
    }
    cout << ans << endl;
    return 0;
}

で分けて何かするのは思い浮かんでいたけど、判定の式がわからなかった。

TCO19 Round3A Med: WaitingForBusAgain

問題概要

原文 → TopCoder Statistics - Problem Statement

種類のバスがあり、 番目のバスは 分おきに停留所に到着することがわかっている。

それぞれのバスについて、来る間隔だけはわかっているがどのタイミングからその間隔で来るかは一様にランダムである。より具体的に言えば、 番目のバスについてある一様乱数 があって、時刻 ( は整数) に停留所に到着する。これらの乱数はそれぞれのバスについて独立に定まる。

このとき、次に停留所に到着するバスのインデックスの期待値を求めよ。

解説

本番出たときは全くわからなかった。

Codeforces のブログに Writer が簡潔に解説を書いている ので、それの前半だけ読んでまたやってみた。

最も頻繁に来るもの、つまり が最も小さいものに着目し、これを とする。バスは 分以内に必ずなにか来るので、長さ のスリットの中にバスがどのように来るかを考えればよい。

まず、各バスについて 以内に到着する確率は である。また、 以内に到着するという条件のもとで考えたときに、( の範囲で) 時刻 に来る確率がどのようになるかを考えたとき、これは の値によらず一様な確率を持つ。このことから、 以内に到着するバスが 台存在するとき、そのうちのどれが最初に到着するかについて、すべて確率 である。

これらを考察すると、 番目のバスまで見て、そのうち 台のバスが 以内に到着するときの期待値 という DP ができる。期待値のテーブルと確率のテーブルを両方持つ必要がある。

ソースコード

struct WaitingForBusAgain {
    double expectedBus(vector<int> f) {
        int N = f.size();
        int mi = *min_element(f.begin(), f.end());

        vector< vector<double> > dp(N+1, vector<double>(N+1));
        vector< vector<double> > prob(N+1, vector<double>(N+1));
        prob[0][0] = 1.0;
        for(int i=0; i<N; i++) {
            double p = 1.0 * mi / f[i];
            for(int j=0; j<=i; j++) {
                if(prob[i][j] == 0) continue;
                
                // slit の中に入れる
                prob[i+1][j+1] += prob[i][j] * p;
                dp[i+1][j+1] += dp[i][j] * p * j / (j+1) + prob[i][j] * p * i / (j+1);

                // slit の中に入れない
                prob[i+1][j  ] += prob[i][j] * (1 - p);
                dp[i+1][j  ] += dp[i][j] * (1 - p);
            }
        }

        double ans = 0.0;
        for(int i=0; i<=N; i++) {
            ans += dp[N][i];
        }
        return ans;
    }
};

最初の言い換えがすべてな気はする、おもしろいね。