はまやんはまやんはまやん

hamayanhamayan's blog

Tsundoku [AtCoder Beginner Contest 172 C]

https://atcoder.jp/contests/abc172/tasks/abc172_c

前提知識

解説

https://atcoder.jp/contests/abc172/submissions/14779347

まずは全探索で考えてみる

机Aからa冊、机Bからb冊取り除くとする。
すると、必要な時間が、A[1]+A[2]+...+A[a] + B[1]+B[2]+...+B[b]となる。
これがK以下であるようなa+bの最小値を答えればいい。
普通にやるとO(NM(N+M))の計算量だけど、A[1]+A[2]+...+A[a]は、以下のような累積和を作っておけば高速に求められる。
Atot[a] = A[1] + A[2] + ... + A[a]
Btot[b] = B[1] + B[2] + ... + B[b]
これの作り方が分からない場合は、累積和でググるといい。
でも計算量はまだO(NM)だ。
1010は間に合わない。107くらいにはしたい。

何か使える性質はないか

aを0から順に増やしていったときに、最適なbはどのように変化するかを観察してみる。
aが増えるということは、Atot[a]が増えていく。
和がK以下である必要があるので、必然的にBtot[b]も小さくなる必要があり、bは小さくなっていく。
aが増えるにしたがってbが小さくなっていくという単調性という性質が見られる。
こういった場合に使えるのが尺取り法

尺取り法

尺取り法の詳しい説明はどこかに任せるので、ググって欲しい。
正直尺取り法でなくても、最適なbを求めるには二分探索を利用してもいい。
こちらでも計算量的には間に合うし、こっちの方が考えることが少なくて良いという人もいる。
尺取り法が分かっていれば、ここからの改善はそんなに難しくない。
前回の最適なbを覚えておいて、そこからbを条件を満たす最大のbとして保ちながら減らしながらa+bの最大を取っていく。

int N, M, K, A[201010], B[201010];
ll Atot[201010], Btot[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, M) cin >> B[i];

    Atot[0] = 0;
    rep(i, 0, N) Atot[i + 1] = Atot[i] + A[i];
    Btot[0] = 0;
    rep(i, 0, M) Btot[i + 1] = Btot[i] + B[i];

    int ans = 0;
    int ok = M;
    rep(a, 0, N + 1) {
        while (0 <= ok && K < Atot[a] + Btot[ok]) ok--;
        if(0 <= ok) chmax(ans, a + ok);
    }
    cout << ans << endl;
}