ABC172-C Tsundoku
(Test/AtCoder/abc172_c.test.cpp)

• View this file on GitHub
• Last update: 2023-07-22 13:55:49+09:00
• Problem: https://atcoder.jp/contests/abc172/tasks/abc172_c

読んだ本の集合が等しいなら本を読んだ合計時間は等しい -> 本を読む順番は考慮しなくて良い。

ここで、 机Aから読む本の冊数を $a$ 冊に固定したとする。机Aから $a$ 冊の本を読むのにかかる時間は $\displaystyle S_{a} = \sum_{i = 1}^{a} A_i$ 分であり、残りの $K - S_{a}$ 分で机Bから何冊よむことができるかを高速に判定できれば良い。

これは $B$ の累積和上で二分探索すれば良い。

Depends on

• 加法群 (Src/Algebra/Group/AdditiveGroup.hpp)
• 1次元累積和 (Src/DataStructure/PrefixSum1D/PrefixSum1D.hpp)
• 静的な列上の区間和クエリ (Src/DataStructure/PrefixSum1D/StaticRangeSumSolver.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Code

#define PROBLEM "https://atcoder.jp/contests/abc172/tasks/abc172_c"

#include "../../Src/Template/TypeAlias.hpp"
#include "../../Src/DataStructure/PrefixSum1D/StaticRangeSumSolver.hpp"

#include <iostream>
#include <vector>
#include <algorithm>

using namespace zawa;

i32 main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    usize N, M; std::cin >> N >> M;
    i64 K; std::cin >> K;

    std::vector<i64> A(N), B(M);
    for (auto& a : A) std::cin >> a;
    for (auto& b : B) std::cin >> b;

    A.push_back((i64)1e15);
    B.push_back((i64)1e15);
    N++; M++;

    Ruisekiwa<i64> SA(A), SB(B);

    u32 ans1{}, ans2{};

    {
        for (u32 a = 0 ; a <= N ; a++) {
            if (SA[a] > K) break;
            u32 v = a + SB.upperBound(0, M, K - SA[a]) - 1;
            ans1 = std::max(ans1, v);
        }
    }

    {
        for (u32 a = 0 ; a <= N ; a++) {
            if (SA[a] > K) break;
            auto f = [&](i64 v) -> bool {
                return SA[a] + v <= K;
            };
            u32 v = a + SB.maxRight(0, f) - 1;
            ans2 = std::max(ans2, v);
        }
    }

    assert(ans1 == ans2);

    std::cout << ans1 << std::endl;
}

#line 1 "Test/AtCoder/abc172_c.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc172/tasks/abc172_c"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 2 "Src/DataStructure/PrefixSum1D/StaticRangeSumSolver.hpp"

#line 2 "Src/Algebra/Group/AdditiveGroup.hpp"

namespace zawa {

template <class T>
class AdditiveGroup {
public:
    using Element = T;
    static constexpr T identity() noexcept {
        return T{};
    }
    static constexpr T operation(const T& l, const T& r) noexcept {
        return l + r;
    }
    static constexpr T inverse(const T& v) noexcept {
        return -v;
    }
};

} // namespace zawa
#line 2 "Src/DataStructure/PrefixSum1D/PrefixSum1D.hpp"

#line 4 "Src/DataStructure/PrefixSum1D/PrefixSum1D.hpp"

#include <cmath>
#include <vector>
#include <cassert>
#include <algorithm>
#include <type_traits>
#include <functional>

namespace zawa {

template <class Group>
class PrefixSum1D {
private:
    using T = typename Group::Element;
    std::vector<T> dat_;

    constexpr bool rangeCheck(u32 l, u32 r) const {
        return (l <= r and r < dat_.size());
    }

public:
    PrefixSum1D() = default; 
    PrefixSum1D(const std::vector<T>& A) : dat_(A.size() + 1, Group::identity()) {
        dat_.shrink_to_fit();
        for (u32 i = 0 ; i < A.size() ; i++) {
            dat_[i + 1] = Group::operation(dat_[i], A[i]);
        }
    }

    inline T operator[](u32 i) const {
        assert(i < dat_.size());
        return dat_[i];
    }

    inline usize size() const {
        return dat_.size();
    }

    T product(u32 l, u32 r) const {
        assert(rangeCheck(l, r));
        return Group::operation(Group::inverse(dat_[l]), dat_[r]);
    }

    u32 lowerBound(u32 l, u32 r, const T& v) const {
        assert(rangeCheck(l, r));
        T value = Group::operation(v, dat_[l]);
        return std::lower_bound(dat_.begin() + l, dat_.begin() + r, value) - dat_.begin();
    }

    u32 upperBound(u32 l, u32 r, const T& v) const {
        assert(rangeCheck(l, r));
        T value = Group::operation(v, dat_[l]);
        return std::upper_bound(dat_.begin() + l, dat_.begin() + r, value) - dat_.begin();
    }

    template <class F>
    u32 maxRight(u32 l, const F& f) const {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(T)>>, "f must be function bool(T)");
        assert(l < dat_.size());
        assert(f(Group::identity()));
        auto f_ = [&](const T& v) -> bool {
            return f(Group::operation(v, Group::inverse(dat_[l])));
        };
        return std::partition_point(dat_.begin() + l, dat_.end(), f_) - dat_.begin();
    }

    template <class F>
    u32 minLeft(u32 r, const F& f) const {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(T)>>, "f must be function bool(T)");
        assert(r < dat_.size());
        assert(f(Group::identity()));
        auto f_ = [&](const T& v) -> bool {
            return f(Group::operation(Group::inverse(v), dat_[r]));
        };
        return dat_.rend() - std::partition_point(dat_.rbegin() + (dat_.size() - r - 1), dat_.rend(), f_) - 1;
    }

    const auto begin() const {
        return dat_.begin();
    }

    const auto end() const {
        return dat_.end();
    }
};

} // namespace zawa
#line 5 "Src/DataStructure/PrefixSum1D/StaticRangeSumSolver.hpp"

namespace zawa {

    template <class T>
    using StaticRangeSumSolver = PrefixSum1D<AdditiveGroup<T>>;

    template <class T>
    using Ruisekiwa = PrefixSum1D<AdditiveGroup<T>>;

};
#line 5 "Test/AtCoder/abc172_c.test.cpp"

#include <iostream>
#line 9 "Test/AtCoder/abc172_c.test.cpp"

using namespace zawa;

i32 main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    usize N, M; std::cin >> N >> M;
    i64 K; std::cin >> K;

    std::vector<i64> A(N), B(M);
    for (auto& a : A) std::cin >> a;
    for (auto& b : B) std::cin >> b;

    A.push_back((i64)1e15);
    B.push_back((i64)1e15);
    N++; M++;

    Ruisekiwa<i64> SA(A), SB(B);

    u32 ans1{}, ans2{};

    {
        for (u32 a = 0 ; a <= N ; a++) {
            if (SA[a] > K) break;
            u32 v = a + SB.upperBound(0, M, K - SA[a]) - 1;
            ans1 = std::max(ans1, v);
        }
    }

    {
        for (u32 a = 0 ; a <= N ; a++) {
            if (SA[a] > K) break;
            auto f = [&](i64 v) -> bool {
                return SA[a] + v <= K;
            };
            u32 v = a + SB.maxRight(0, f) - 1;
            ans2 = std::max(ans2, v);
        }
    }

    assert(ans1 == ans2);

    std::cout << ans1 << std::endl;
}

Back to top page