ABC229-D Longest X
(Test/AtCoder/abc229_d.test.cpp)

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

$S$ において、l文字目からr - 1文字目すべてをXに変えることが可能か？という問題を考える。

これはl文字目からr - 1文字までに.が $K$ 個以内であれば良い。

このような判定問題はあらかじめ.の数について累積和をとっておくことで定数時間で可能である。

この上で、 Xを連続させる区間の左端を固定した上で右端を可能な限り伸ばすことを考える -> 二分探索でそのような右端の最大が $O(\log \mid S\mid)$ で求まる。

よって左端を全探索することで $O(\mid S\mid \log \mid S\mid)$ でこの問題を解くことができた。

(尺取りの方が頭にやさしそう)

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/abc229/tasks/abc229_d"

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

using namespace zawa;

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

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

    std::string S;
    std::cin >> S;
    u32 K;
    std::cin >> K;

    std::vector<i32> A(S.size());
    for (u32 i = 0 ; i < S.size() ; i++) {
        A[i] = S[i] == '.';
    }
    A.push_back(K + 1);

    Ruisekiwa<i32> pref(A);

    u32 ans = 0;
    for (u32 i = 0 ; i <= S.size() ; i++) {
        u32 v = pref.upperBound(i, pref.size() - 1, K) - 1;
        ans = std::max(ans, v - i);
    }

    std::cout << ans << std::endl;
}

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

#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/abc229_d.test.cpp"

using namespace zawa;

#include <iostream>
#line 11 "Test/AtCoder/abc229_d.test.cpp"

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

    std::string S;
    std::cin >> S;
    u32 K;
    std::cin >> K;

    std::vector<i32> A(S.size());
    for (u32 i = 0 ; i < S.size() ; i++) {
        A[i] = S[i] == '.';
    }
    A.push_back(K + 1);

    Ruisekiwa<i32> pref(A);

    u32 ans = 0;
    for (u32 i = 0 ; i <= S.size() ; i++) {
        u32 v = pref.upperBound(i, pref.size() - 1, K) - 1;
        ans = std::max(ans, v - i);
    }

    std::cout << ans << std::endl;
}

Back to top page