[AtCoder] ABC 172 C – Tsundoku

2020年6月27日2020年12月14日

問題

方針

累積和と二分探索

机 \( A \) の本を \( i \) 冊読んだとき、机 \( B \) の本を最大でいくつ読むことができるかを考えます。机 \( A \) の本を \( i \) 冊読むのにかかる時間は、累積和で求めることができます。残り時間が \( t \) 分のとき、机 \( B \) の本を何冊読むことができるかは、累積和と二分探索で求めることができます。

しゃくとり法

しゃくとり法という言葉が適切かどうかは分かりませんが、似たような発想で解きます。まず初めに、机 \( A \) の本を最大まで読むことができる冊数を \( a \) とします。次に、机 \( A \) の本を \( a \) 冊読んだとき、机 \( B \) の最大まで読むことができる冊数を \( b \) とします。このとき、\( a + b \) 冊読んだことになります。次に、机 \( A \) の本を \( a – 1 \) 冊読んだとき、机 \( B \) の本をいくつまで読めるかを考えます。このとき、机 \( B \) の本は \( b \) 冊読めることが確定しているので、\( b + 1 \) 冊目以降から探索すれば良いです。したがって、机 \( A \) の本を \( a \) から \( 0 \) 冊まで読んだとき、机 \( B \) の本を最大でいくつ読むことができるかが分かります。

コード

累積和と二分探索

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N, M;
    ll K;
    cin >> N >> M >> K;
    ll A[N], B[M];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < M; i++) {
        cin >> B[i];
    }
    int ans = 0;
    ll c[M + 1]{};
    for (int i = 0; i < M; i++) {
        c[i + 1] = c[i] + B[i];
    }
    ll t = 0;
    for (int i = 0; i <= N; i++) {
        if (i != 0) {
            t += A[i - 1];
        }
        if (t > K) break;
        int l = -1;
        int r = M + 1;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (t + c[m] <= K) {
                l = m;
            } else {
                r = m;
            }
        }
        ans = max(ans, i + l);
    }
    cout << ans << "\n";
    return 0;
}

しゃくとり法

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N, M;
    ll K;
    cin >> N >> M >> K;
    ll A[N + 1]{}, B[M + 1]{};
    ll t = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i + 1];
    }
    for (int i = 0; i < M; i++) {
        cin >> B[i + 1];
    }
    int id_a = 0;
    for (int i = 0; i <= N; i++) {
        if (t + A[i] <= K) {
            t += A[i];
            id_a = i;
        } else {
            break;
        }
    }
    int ans = id_a;
    int id_b = 0;
    for (int i = id_a; i >= 0; i--) {
        while (id_b <= M) {
            if (t + B[id_b] <= K) {
                t += B[id_b];
                ans = max(ans, i + id_b);
                id_b++;
            } else {
                break;
            }
        }
        t -= A[i];
    }
    cout << ans << "\n";
    return 0;
}