cp-documentation

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: AOJ3548 String Puzzle
(Test/AOJ/3548.test.cpp)

$A$の各要素を長さ$1$の文字列として、$A$を構築できないならば$-1$になる。

そうでないならば、区間スケジューリング問題に帰着する。区間スケジューリング問題を解くアルゴリズムに思いを馳せると、考慮すべき区間の数を減らすことができる。

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * AOJ3548 String Puzzle
 * https://onlinejudge.u-aizu.ac.jp/status/users/zawakasu/submissions/1/3548/judge/10394036/C++20
 */

#include <iostream>
#include <string>
#include <unordered_set>

#include "../../Src/Sequence/EnumerateStaticLengthProduct.hpp"
#include "../../Src/Algebra/Monoid/RollingHashMonoid.hpp"

using namespace zawa;

using Monoid = RollingHashMonoid;
using E = Monoid::Element;
using V = E::Value;

V E::base{
    E::randomValue(26)
};

std::vector<E> input() {
    std::string S;
    std::cin >> S;
    std::vector<E> A(S.size());
    for (int i{} ; i < (int)S.size() ; i++) {
        A[i] = E{S[i]};
    }
    return A;
}

bool check(const std::vector<E>& S, const std::vector<E>& T) {
    std::unordered_set<V> set;
    for (const auto& hash : T) set.insert(hash.hash);
    bool ok{true};
    for (const auto& hash : S) ok &= set.find(hash.hash) != set.end();
    return ok;
}

int solve() {
    int N, M, K;
    std::cin >> N >> M >> K;
    std::vector<E> S(input());
    std::vector<E> T(input());
    if (!check(S, T)) return -1;
    std::unordered_set<V> set;
    for (const auto& hash : EnumerateStaticLengthProduct<Monoid>(T, K)) {
        set.insert(hash.hash);
    }
    std::vector<E> P(EnumerateStaticLengthProduct<Monoid>(S, K));
    int ans{};
    for (int i{} ; i < (int)P.size() ; ) {
        if (set.find(P[i].hash) == set.end()) {
            i++;
        }
        else {
            ans++;
            i += K;
        }
    }
    return ans;
}

int main() {
#ifdef ONLINE_JUDGE
    std::cout << solve() << '\n';
#else
    std::cout << "Hello World" << '\n';
#endif
}
#line 1 "Test/AOJ/3548.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * AOJ3548 String Puzzle
 * https://onlinejudge.u-aizu.ac.jp/status/users/zawakasu/submissions/1/3548/judge/10394036/C++20
 */

#include <iostream>
#include <string>
#include <unordered_set>

#line 2 "Src/Sequence/EnumerateStaticLengthProduct.hpp"

#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/Algebra/Semigroup/SemigroupConcept.hpp"

#include <concepts>

namespace zawa {

namespace concepts {

template <class T>
concept Semigroup = requires {
    typename T::Element;
    { T::operation(std::declval<typename T::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

} // namespace concepts

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

#line 2 "Src/DataStructure/SWAG/SWAGable.hpp"

#line 2 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 4 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 6 "Src/Algebra/Monoid/MonoidConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Identitiable = requires {
    typename T::Element;
    { T::identity() } -> std::same_as<typename T::Element>;
};

template <class T>
concept Monoid = Semigroup<T> and Identitiable<T>;

} // namespace

} // namespace zawa
#line 5 "Src/DataStructure/SWAG/SWAGable.hpp"

#line 7 "Src/DataStructure/SWAG/SWAGable.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept SWAGable = requires {
    typename T::Element;
    typename T::Fold;
    typename T::Fold::Element;
    { T::convert(std::declval<typename T::Element>()) } -> std::same_as<typename T::Fold::Element>;
    { T::pushBack(std::declval<typename T::Fold::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Fold::Element>;
    { T::pushFront(std::declval<typename T::Fold::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Fold::Element>;
};

} // namespace concepts

template <concepts::Semigroup S>
class SemigroupSWAGable {
public:
    using Element = typename S::Element;
    using Fold = S;
    using F = Fold::Element;
    static F convert(Element v) {
        return v;
    }
    static F pushBack(F f, Element v) {
        return S::operation(f, v);
    }
    static F pushFront(F f, Element v) {
        return S::operation(v, f);
    }
    static F operation(F l, F r) {
        return S::operation(l, r);
    }
};

template <concepts::Monoid S>
class MonoidSWAGable {
public:
    using Element = typename S::Element;
    using Fold = S;
    using F = Fold::Element;
    static F convert(Element v) {
        return v;
    }
    static F pushBack(F f, Element v) {
        return S::operation(f, v);
    }
    static F pushFront(F f, Element v) {
        return S::operation(v, f);
    }
    static F identity() {
        return S::identity();
    }
    static F operation(F l, F r) {
        return S::operation(l, r);
    }
};

} // namespace zawa
#line 7 "Src/DataStructure/SWAG/FoldableQueue.hpp"

#include <cassert>
#include <optional>
#include <vector>

namespace zawa {

template <concepts::SWAGable S>
class FoldableQueue {
public:

    using V = typename S::Element;
    using Fold = typename S::Fold;
    using F = typename Fold::Element;

    FoldableQueue() = default;

    usize size() const noexcept {
        return m_front.size() + m_back.size();
    }

    bool empty() const noexcept {
        return size() == 0u;
    }

    void push(const V& v) {
        m_raw.push_back(v);
        m_back.push_back(m_back.size() ? S::pushBack(m_back.back(), v) : S::convert(v));
    }

    void pop() {
        assert(size());
        move();
        m_front.pop_back();
    }

    std::pair<F, F> get() const requires concepts::Identitiable<typename S::Fold> {
        return {
            m_front.empty() ? Fold::identity() : m_front.back(),
            m_back.empty() ? Fold::identity() : m_back.back()
        };
    }

    std::pair<std::optional<F>, std::optional<F>> get() const {
        return {
            m_front.empty() ? std::nullopt : std::optional<F>{m_front.back().first},
            m_back.empty() ? std::nullopt : std::optional<F>{m_back.back().first}
        };
    }

    F product() const requires concepts::Monoid<typename S::Fold> {
        auto [f, b] = get();
        return Fold::operation(f, b);
    }

    F product() const requires concepts::Semigroup<typename S::Fold> {
        assert(m_front.size() or m_back.size());
        if (m_front.empty()) return m_back.back().first;
        if (m_back.empty()) return m_front.back().first;
        return S::Fold::operation(m_front.back().first, m_back.back().first);
    }
    
private:
    std::vector<F> m_front{}, m_back{};
    std::vector<V> m_raw{};

    void move() {
        if (m_front.size()) return;
        while (m_back.size()) {
            m_back.pop_back();
            V v{m_raw.back()};
            m_raw.pop_back();
            m_front.push_back(m_front.size() ? S::pushFront(m_front.back(), v) : S::convert(v));
        }
    }
};

} // namespace zawa
#line 6 "Src/Sequence/EnumerateStaticLengthProduct.hpp"

#line 8 "Src/Sequence/EnumerateStaticLengthProduct.hpp"
#include <iterator>
#include <type_traits>
#line 11 "Src/Sequence/EnumerateStaticLengthProduct.hpp"

namespace zawa {

template <concepts::Semigroup S>
std::vector<typename S::Element> EnumerateStaticLengthProduct(const std::vector<typename S::Element>& A, usize K) {
    assert(K > 0);
    if (A.size() < K) return {};
    std::vector<typename S::Element> res(A.size() - K + 1);
    FoldableQueue<SemigroupSWAGable<S>> que{};
    for (usize i{} ; i < K ; i++) {
        que.push(A[i]);
    }
    for (usize i{} ; i < A.size() - K ; i++) {
        res[i] = que.product();
        que.pop();
        que.push(A[i + K]);
    }
    res[A.size() - K] = que.product();
    return res;
}

} // namespace zawa
#line 2 "Src/Algebra/Monoid/RollingHashMonoid.hpp"

#line 2 "Src/Number/Mersenne61ModInt.hpp"

#line 4 "Src/Number/Mersenne61ModInt.hpp"

namespace zawa {

// @reference: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
class Mersenne61ModInt {
public:
    using Value = u64;
private:
    static constexpr Value MOD{(1ull << 61) - 1}; // == MASK61
    static constexpr Value MASK30{(1ull << 30) - 1};
    static constexpr Value MASK31{(1ull << 31) - 1};
    Value v_{};
public:
    constexpr Mersenne61ModInt() {}

    static constexpr Value Mod() noexcept {
        return MOD;
    }
    static constexpr Value Modulo(const Value& v) noexcept {
        Value res{(v >> 61) + (v & MOD)};
        res = (res >= MOD ? res - MOD : res);
        return res;
    }
    static constexpr Value UnsafeMul(const Value& a, const Value& b) noexcept {
        Value fa{a >> 31}, fb{b >> 31};
        Value ba{a & MASK31}, bb{b & MASK31};
        Value mid{fa * bb + fb * ba};
        return Value{2}*fa*fb + (mid >> 30) + ((mid & MASK30) << 31) + ba*bb;
    }
    static constexpr Value Mul(const Value& a, const Value& b) noexcept {
        return Modulo(UnsafeMul(a, b));
    }
};

};
#line 5 "Src/Algebra/Monoid/RollingHashMonoid.hpp"

#include <random>
#line 8 "Src/Algebra/Monoid/RollingHashMonoid.hpp"

namespace zawa {

struct RollingHashMonoidData {
    using Value = Mersenne61ModInt::Value;
    using Size = usize;
    static Value base;
    Value hash{}, pow{1};
    usize len{};

    constexpr RollingHashMonoidData() = default;
    constexpr RollingHashMonoidData(Value h, Value p, usize l) : hash{h}, pow{p}, len{l} {}
    template <class T>
    constexpr RollingHashMonoidData(const T& v) 
        : hash{static_cast<Value>(v)}, pow{base}, len{1} {}
    // RollingHashMonoidData(const RollingHashMonoidData& data)
    //     : hash{data.hash}, pow{data.pow}, len{data.len} {}
    
    static Value randomValue(const Value& sigma) {
        return std::mt19937{std::random_device{}()}() % (Mersenne61ModInt::Mod() - sigma) + sigma + 1;
    }

    friend constexpr bool operator==(const RollingHashMonoidData& lhs, const RollingHashMonoidData& rhs) {
        return lhs.hash == rhs.hash and lhs.len == rhs.len;
    }
    friend constexpr bool operator!=(const RollingHashMonoidData& lhs, const RollingHashMonoidData& rhs) {
        return lhs.hash != rhs.hash or lhs.len != rhs.len;
    }
};

struct RollingHashMonoid {
    using Modulo = Mersenne61ModInt;
    using Element = RollingHashMonoidData;
    static constexpr Element identity() noexcept {
        return Element{};
    }
    static constexpr Element operation(const Element& lhs, const Element& rhs) noexcept {
        return Element{
            Modulo::Modulo(Modulo::UnsafeMul(lhs.hash, rhs.pow) + rhs.hash),
            Modulo::Mul(lhs.pow, rhs.pow),
            lhs.len + rhs.len
        };
    }
};

} // namespace zawa
#line 14 "Test/AOJ/3548.test.cpp"

using namespace zawa;

using Monoid = RollingHashMonoid;
using E = Monoid::Element;
using V = E::Value;

V E::base{
    E::randomValue(26)
};

std::vector<E> input() {
    std::string S;
    std::cin >> S;
    std::vector<E> A(S.size());
    for (int i{} ; i < (int)S.size() ; i++) {
        A[i] = E{S[i]};
    }
    return A;
}

bool check(const std::vector<E>& S, const std::vector<E>& T) {
    std::unordered_set<V> set;
    for (const auto& hash : T) set.insert(hash.hash);
    bool ok{true};
    for (const auto& hash : S) ok &= set.find(hash.hash) != set.end();
    return ok;
}

int solve() {
    int N, M, K;
    std::cin >> N >> M >> K;
    std::vector<E> S(input());
    std::vector<E> T(input());
    if (!check(S, T)) return -1;
    std::unordered_set<V> set;
    for (const auto& hash : EnumerateStaticLengthProduct<Monoid>(T, K)) {
        set.insert(hash.hash);
    }
    std::vector<E> P(EnumerateStaticLengthProduct<Monoid>(S, K));
    int ans{};
    for (int i{} ; i < (int)P.size() ; ) {
        if (set.find(P[i].hash) == set.end()) {
            i++;
        }
        else {
            ans++;
            i += K;
        }
    }
    return ans;
}

int main() {
#ifdef ONLINE_JUDGE
    std::cout << solve() << '\n';
#else
    std::cout << "Hello World" << '\n';
#endif
}
Back to top page