#1192193 (C++23(gcc16)) No.3757 Happy End

• 問題: No.3757 Happy End
• ユーザー: 秋ナス🍆
• 提出日時: 2026-10-09 21:30:18
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 22,517 bytes
• コンパイル時間: 5,120 ms
• コンパイル使用メモリ: 400,968 KB
• 実行使用メモリ: 9,904 KB
• 最終ジャッジ日時: 2026-10-09 21:30:34
• 合計ジャッジ時間: 7,895 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge4_0

ファイルパターン	結果
sample	AC * 3
other	AC * 47

ソースコード

#include <bits/stdc++.h>
using namespace std;

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

#if defined(__unix__) || defined(__APPLE__)
#include <unistd.h>
#endif

template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v);

template <typename T1, typename T2>
std::istream& operator>>(std::istream& is, std::pair<T1, T2>& p);

template <typename... Args>
std::istream& operator>>(std::istream& is, std::tuple<Args...>& t);

namespace input_detail {

#ifdef LOCAL

inline std::size_t& read_count() {
    static std::size_t count = 0;
    return count;
}

inline bool& failed_read() {
    static bool failed = false;
    return failed;
}

inline bool stdin_is_terminal() {
#if defined(__unix__) || defined(__APPLE__)
    return isatty(fileno(stdin));
#else
    return false;
#endif
}

struct EndOfInputChecker {
    ~EndOfInputChecker() {
        if (stdin_is_terminal() || failed_read() || std::cin.bad()) return;

        std::cin >> std::ws;
        std::string token;
        if (std::cin >> token) {
            std::cerr << "[input error] 入力が余っています。\n"
                      << "  最初に余った値: " << token << '\n'
                      << "  N と M、H と W、辺数 m、配列長 n などを間違えていないか確認してください。\n";
            std::abort();
        }
    }
};

inline void ensure_end_checker() {
    static EndOfInputChecker checker;
    (void)checker;
}

inline void begin_input() {
    ensure_end_checker();
}

template <typename T>
void read_one(std::istream& is, T& value) {
    if (&is != &std::cin) {
        is >> value;
        return;
    }
    ensure_end_checker();
    ++read_count();
    if (!(is >> value)) {
        failed_read() = true;
        std::cerr << "[input error] 入力が足りないか、型が合いません。\n"
                  << "  " << read_count() << " 個目の値を読み込めませんでした。\n"
                  << "  N と M、H と W、辺数 m、配列長 n などを間違えていないか確認してください。\n";
        std::abort();
    }
}

#else

inline void begin_input() {
}

template <typename T>
void read_one(std::istream& is, T& value) {
    is >> value;
}

#endif

template <typename... Args>
void read_values(Args&... args) {
    (read_one(std::cin, args), ...);
}

}

struct FastIO {
    FastIO() {
        std::ios_base::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
};
inline FastIO fast_io_init;

template <typename T1, typename T2>
std::istream& operator>>(std::istream& is, std::pair<T1, T2>& p) {
    input_detail::read_one(is, p.first);
    input_detail::read_one(is, p.second);
    return is;
}

template <typename Tuple, std::size_t... I>
void read_tuple_impl(std::istream& is, Tuple& t, std::index_sequence<I...>) {
    (..., input_detail::read_one(is, std::get<I>(t)));
}

template <typename... Args>
std::istream& operator>>(std::istream& is, std::tuple<Args...>& t) {
    read_tuple_impl(is, t, std::index_sequence_for<Args...>{});
    return is;
}

template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
    for (auto& elem : v) {
        input_detail::read_one(is, elem);
    }
    return is;
}

template <typename T>
struct is_pair : std::false_type {};
template <typename T1, typename T2>
struct is_pair<std::pair<T1, T2>> : std::true_type {};

template <typename T>
struct is_tuple : std::false_type {};
template <typename... Args>
struct is_tuple<std::tuple<Args...>> : std::true_type {};

template <typename T>
struct is_vector : std::false_type {};
template <typename T>
struct is_vector<std::vector<T>> : std::true_type {};

template <typename T>
void adjust_zero_indexed(T& val) {
    using DecayedT = std::decay_t<T>;
    if constexpr (is_pair<DecayedT>::value) {
        adjust_zero_indexed(val.first);
        adjust_zero_indexed(val.second);
    } else if constexpr (is_tuple<DecayedT>::value) {
        std::apply([](auto&... args) { (adjust_zero_indexed(args), ...); }, val);
    } else if constexpr (is_vector<DecayedT>::value) {
        for (auto& elem : val) {
            adjust_zero_indexed(elem);
        }
    } else if constexpr (std::is_arithmetic_v<DecayedT> && !std::is_same_v<DecayedT, char> && !std::is_same_v<DecayedT, signed char> &&
                         !std::is_same_v<DecayedT, unsigned char> && !std::is_same_v<DecayedT, wchar_t> &&
#if defined(__cpp_char8_t)
                         !std::is_same_v<DecayedT, char8_t> &&
#endif
                         !std::is_same_v<DecayedT, char16_t> && !std::is_same_v<DecayedT, char32_t> && !std::is_same_v<DecayedT, bool>) {
        --val;
    } else {

    }
}

using default_type = long;

template <typename... Args>
void read(Args&... args) {
    input_detail::read_values(args...);
}

template <typename T = default_type>
T read_val() {
    T val;
    input_detail::read_one(std::cin, val);
    return val;
}

template <typename T1 = default_type, typename T2 = default_type>
std::pair<T1, T2> read_pair() {
    std::pair<T1, T2> p;
    input_detail::begin_input();
    std::cin >> p;
    return p;
}

template <typename... Args>
std::tuple<Args...> read_tuple() {
    std::tuple<Args...> t;
    input_detail::begin_input();
    std::cin >> t;
    return t;
}

template <typename T = default_type, typename Size, std::enable_if_t<std::is_integral_v<Size> && !std::is_same_v<Size, bool>, int> = 0>
std::vector<T> read_vec(Size n, bool zero_indexed = false) {
    std::vector<T> v(n);
    input_detail::begin_input();
    std::cin >> v;
    if (zero_indexed) {
        adjust_zero_indexed(v);
    }
    return v;
}

template <typename T = default_type>
std::vector<T> read_vec(bool zero_indexed = false) {
    int n;
    input_detail::read_one(std::cin, n);
    return read_vec<T>(n, zero_indexed);
}

template <typename T1 = default_type, typename T2 = default_type, typename Size,
          std::enable_if_t<std::is_integral_v<Size> && !std::is_same_v<Size, bool>, int> = 0>
std::vector<std::pair<T1, T2>> read_vec_pair(Size n, bool zero_indexed = false) {
    return read_vec<std::pair<T1, T2>>(n, zero_indexed);
}

template <typename T1 = default_type, typename T2 = default_type>
std::vector<std::pair<T1, T2>> read_vec_pair(bool zero_indexed = false) {
    int n;
    input_detail::read_one(std::cin, n);
    return read_vec_pair<T1, T2>(n, zero_indexed);
}

template <typename... Args, typename Size, std::enable_if_t<std::is_integral_v<Size> && !std::is_same_v<Size, bool>, int> = 0>
std::vector<std::tuple<Args...>> read_vec_tuple(Size n, bool zero_indexed = false) {
    return read_vec<std::tuple<Args...>>(n, zero_indexed);
}

template <typename... Args>
std::vector<std::tuple<Args...>> read_vec_tuple(bool zero_indexed = false) {
    int n;
    input_detail::read_one(std::cin, n);
    return read_vec_tuple<Args...>(n, zero_indexed);
}

template <typename T = default_type>
std::vector<std::vector<T>> read_vec_grid(int h, int w, bool zero_indexed = false) {
    std::vector<std::vector<T>> grid(h, std::vector<T>(w));
    input_detail::begin_input();
    std::cin >> grid;
    if (zero_indexed) {
        adjust_zero_indexed(grid);
    }
    return grid;
}

template <typename T = default_type>
std::vector<std::vector<T>> read_vec_grid(bool zero_indexed = false) {
    int h, w;
    input_detail::read_values(h, w);
    return read_vec_grid<T>(h, w, zero_indexed);
}

template <typename T = default_type, typename Size, std::enable_if_t<std::is_integral_v<Size> && !std::is_same_v<Size, bool>, int> = 0>
std::vector<std::vector<T>> read_vec_var(Size n, bool zero_indexed = false) {
    std::vector<std::vector<T>> res(n);
    input_detail::begin_input();
    for (int i = 0; i < static_cast<int>(n); ++i) {
        int m;
        input_detail::read_one(std::cin, m);
        res[i] = read_vec<T>(m, zero_indexed);
    }
    return res;
}

template <typename T = default_type>
std::vector<std::vector<T>> read_vec_var(bool zero_indexed = false) {
    int n;
    input_detail::read_one(std::cin, n);
    return read_vec_var<T>(n, zero_indexed);
}

template <typename T = default_type>
T read_zero_idx() {
    T val;
    input_detail::read_one(std::cin, val);
    adjust_zero_indexed(val);
    return val;
}

inline std::vector<std::vector<int>> read_graph(int n, int m, bool directed = false) {
    std::vector<std::vector<int>> g(n);
    input_detail::begin_input();
    for (int i = 0; i < m; ++i) {
        int u = read_zero_idx<int>();
        int v = read_zero_idx<int>();
        g[u].push_back(v);
        if (!directed) {
            g[v].push_back(u);
        }
    }
    return g;
}

inline std::vector<std::vector<int>> read_graph(bool directed = false) {
    int n, m;
    input_detail::read_values(n, m);
    return read_graph(n, m, directed);
}

template <typename Cost = default_type>
struct Edge {
    int to;
    Cost cost;

    Edge() = default;
    Edge(int to, Cost cost) : to(to), cost(cost) {}
};

template <typename Cost = default_type>
inline std::vector<std::vector<Edge<Cost>>> read_weighted_graph(int n, int m, bool directed = false) {
    std::vector<std::vector<Edge<Cost>>> g(n);
    input_detail::begin_input();
    for (int i = 0; i < m; ++i) {
        int u = read_zero_idx<int>();
        int v = read_zero_idx<int>();
        Cost w;
        input_detail::read_one(std::cin, w);
        g[u].push_back(Edge<Cost>{v, w});
        if (!directed) {
            g[v].push_back(Edge<Cost>{u, w});
        }
    }
    return g;
}

template <typename Cost = default_type>
inline std::vector<std::vector<Edge<Cost>>> read_weighted_graph(bool directed = false) {
    int n, m;
    input_detail::read_values(n, m);
    return read_weighted_graph<Cost>(n, m, directed);
}

#include <iterator>
#include <optional>
#include <print>
#include <string>
#include <string_view>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

namespace output_detail {

template <typename T>
struct is_string_like {
   private:
    using U = std::remove_cvref_t<T>;

    static constexpr bool is_char_array = std::is_array_v<U> && std::is_same_v<std::remove_cv_t<std::remove_extent_t<U>>, char>;

    static constexpr bool is_char_pointer = std::is_pointer_v<U> && std::is_same_v<std::remove_cv_t<std::remove_pointer_t<U>>, char>;

   public:
    static constexpr bool value = std::is_same_v<U, std::string> || std::is_same_v<U, std::string_view> || is_char_array || is_char_pointer;
};

template <typename T>
inline constexpr bool is_string_like_v = is_string_like<T>::value;

template <typename T, typename = void>
struct is_iterable : std::false_type {};

template <typename T>
struct is_iterable<T, std::void_t<decltype(std::begin(std::declval<const T&>())), decltype(std::end(std::declval<const T&>()))>>
    : std::bool_constant<!is_string_like_v<T>> {};

template <typename T>
inline constexpr bool is_iterable_v = is_iterable<T>::value;

}

template <typename T>
struct Plus1Wrapper {
    const T& val;
};

namespace output_detail {

template <typename T, typename = void>
struct is_plus1_supported : std::false_type {};

template <typename T>
struct is_plus1_supported<
    T, std::enable_if_t<std::is_arithmetic_v<std::remove_cvref_t<T>> && !std::is_same_v<std::remove_cvref_t<T>, bool> &&
                        !std::is_same_v<std::remove_cvref_t<T>, char> && !std::is_same_v<std::remove_cvref_t<T>, signed char> &&
                        !std::is_same_v<std::remove_cvref_t<T>, unsigned char> && !std::is_same_v<std::remove_cvref_t<T>, wchar_t> &&
#if defined(__cpp_char8_t)
                        !std::is_same_v<std::remove_cvref_t<T>, char8_t> &&
#endif
                        !std::is_same_v<std::remove_cvref_t<T>, char16_t> && !std::is_same_v<std::remove_cvref_t<T>, char32_t>>>
    : std::true_type {
};

template <typename T1, typename T2>
struct is_plus1_supported<std::pair<T1, T2>> : std::bool_constant<is_plus1_supported<T1>::value && is_plus1_supported<T2>::value> {};

template <typename... Args>
struct is_plus1_supported<std::tuple<Args...>> : std::bool_constant<(is_plus1_supported<Args>::value && ...)> {};

template <typename T>
struct is_plus1_supported<T, std::void_t<decltype(std::begin(std::declval<const T&>())), decltype(std::end(std::declval<const T&>())),
                                         decltype(*std::begin(std::declval<const T&>()))>>
    : std::bool_constant<!is_string_like_v<T> &&
                         is_plus1_supported<std::remove_cvref_t<decltype(*std::begin(std::declval<const T&>()))>>::value> {};

template <typename T>
inline constexpr bool is_plus1_supported_v = is_plus1_supported<std::remove_cvref_t<T>>::value;

}

template <typename T>
    requires output_detail::is_plus1_supported_v<T>
constexpr Plus1Wrapper<T> plus1(const T& x) {
    return Plus1Wrapper<T>{x};
}

template <typename T>
void print_val(const T& val);

template <typename T, typename U>
void print_val(const std::pair<T, U>& p);

template <typename... Args>
void print_val(const std::tuple<Args...>& t);

template <typename T>
void print_val(const std::optional<T>& opt);

template <typename T, typename U>
void print_val(const Plus1Wrapper<std::pair<T, U>>& w);

template <typename... Args>
void print_val(const Plus1Wrapper<std::tuple<Args...>>& w);

template <typename T>
void print_val(const Plus1Wrapper<T>& w);

namespace output_detail {

template <typename Func, typename... Args>
void print_separated(Func&& print_one, const Args&... args) {
    bool first = true;

    auto emit = [&](const auto& x) {
        if (!first) {
            std::print(" ");
        }

        first = false;
        print_one(x);
    };

    (emit(args), ...);
}

}

template <typename T>
void print_val(const T& val) {
    if constexpr (output_detail::is_iterable_v<T>) {
        bool first = true;

        for (const auto& item : val) {
            if (!first) {
                std::print(" ");
            }

            first = false;
            print_val(item);
        }
    } else {
        std::print("{}", val);
    }
}

template <typename T, typename U>
void print_val(const std::pair<T, U>& p) {
    print_val(p.first);
    std::print(" ");
    print_val(p.second);
}

namespace output_detail {

template <typename Tuple, std::size_t... I>
void print_tuple_impl(const Tuple& t, std::index_sequence<I...>) {
    print_separated([](const auto& x) { print_val(x); }, std::get<I>(t)...);
}

}

template <typename... Args>
void print_val(const std::tuple<Args...>& t) {
    output_detail::print_tuple_impl(t, std::index_sequence_for<Args...>{});
}

template <typename T>
void print_val(const std::optional<T>& opt) {
    if (opt.has_value()) {
        print_val(*opt);
    } else {
        std::print("-1");
    }
}

template <typename T, typename U>
void print_val(const Plus1Wrapper<std::pair<T, U>>& w) {
    print_val(plus1(w.val.first));
    std::print(" ");
    print_val(plus1(w.val.second));
}

namespace output_detail {

template <typename Tuple, std::size_t... I>
void print_plus1_tuple_impl(const Tuple& t, std::index_sequence<I...>) {
    print_separated([](const auto& x) { print_val(plus1(x)); }, std::get<I>(t)...);
}

}

template <typename... Args>
void print_val(const Plus1Wrapper<std::tuple<Args...>>& w) {
    output_detail::print_plus1_tuple_impl(w.val, std::index_sequence_for<Args...>{});
}

template <typename T>
void print_val(const Plus1Wrapper<T>& w) {
    if constexpr (output_detail::is_iterable_v<T>) {
        bool first = true;

        for (const auto& item : w.val) {
            if (!first) {
                std::print(" ");
            }

            first = false;
            print_val(plus1(item));
        }
    } else {
        print_val(w.val + 1);
    }
}

template <typename Container>
void out_1indexed(const Container& c) {
    auto it = std::begin(c);

    if (it != std::end(c)) {
        ++it;
    }

    bool first = true;

    for (; it != std::end(c); ++it) {
        if (!first) {
            std::print(" ");
        }

        first = false;
        print_val(*it);
    }

    std::println();
}

template <typename Container>
void out_from1(const Container& c) {
    out_1indexed(c);
}

inline void out() {
    std::println();
}

template <typename... Args>
void out(const Args&... args) {
    output_detail::print_separated([](const auto& x) { print_val(x); }, args...);

    std::println();
}

template <typename... Args>
void pr(const Args&... args) {
    out(args...);
}

template <typename Container>
void out_lines(const Container& c) {
    for (const auto& x : c) {
        print_val(x);
        std::println();
    }
}

template <typename Grid>
void out_grid(const Grid& grid) {
    for (const auto& row : grid) {
        out(row);
    }
}

inline void Yes(bool condition = true, std::string_view true_str = "Yes", std::string_view false_str = "No") {
    std::println("{}", condition ? true_str : false_str);
}

inline void No(bool condition = true) {
    Yes(!condition);
}
#include <istream>
#include <numeric>
#include <print>
#include <ranges>
#include <vector>

#define ALL(a) (a).begin(), (a).end()
using i128 = __int128;

template <typename T, typename U>
inline bool chmin(T& a, const U& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <typename T, typename U>
inline bool chmax(T& a, const U& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <std::integral T>
inline T div_ceil(T a, T b) {
    if (a > 0) return a / b + (a % b != 0);
    return a / b;
}

template <std::integral T>
inline T div_floor(T a, T b) {
    if (a < 0) return a / b - (a % b != 0);
    return a / b;
}

template <std::integral T>
inline T mod(T a, T m) {
    a %= m;
    if (a < 0) a += m;
    return a;
}

template <typename T>
inline constexpr T INF = std::numeric_limits<T>::max() / 2;

template <>
inline constexpr float INF<float> = std::numeric_limits<float>::infinity();

template <>
inline constexpr double INF<double> = std::numeric_limits<double>::infinity();

template <>
inline constexpr long double INF<long double> = std::numeric_limits<long double>::infinity();

template <typename T>
auto make_vector(size_t size, T&& initial_value) {
    return std::vector<std::decay_t<T>>(size, std::forward<T>(initial_value));
}

template <typename... Args>
auto make_vector(size_t size, Args&&... args) {
    auto inner = make_vector(std::forward<Args>(args)...);
    return std::vector<decltype(inner)>(size, inner);
}

template <typename T = int>
inline std::vector<T> iota_vec(int n, T start = 0) {
    std::vector<T> v(n);
    std::iota(v.begin(), v.end(), start);
    return v;
}

template <typename T>
inline std::vector<T> doubled_vec(const std::vector<T>& v) {
    std::vector<T> res;
    res.reserve(v.size() * 2);
    res.insert(res.end(), v.begin(), v.end());
    res.insert(res.end(), v.begin(), v.end());
    return res;
}

inline bool is_palindrome(std::string_view s) {
    return std::ranges::equal(s, s | std::views::reverse);
}

#ifdef LOCAL
#include <utility/debug.hpp>
#else
#define debug(...)
#endif

#include <concepts>
#include <ranges>
#include <vector>

struct KMP {

    template <std::ranges::random_access_range Seq>
        requires std::ranges::sized_range<Seq>
    static std::vector<int> build_mp(const Seq& s) {
        const int n = static_cast<int>(std::ranges::size(s));
        std::vector<int> mp(n + 1);
        mp[0] = -1;
        int j = -1;
        for (int i = 0; i < n; i++) {
            while (j >= 0 && s[i] != s[j])
                j = mp[j];
            j++;
            mp[i + 1] = j;
        }
        return mp;
    }

    template <std::ranges::random_access_range Text, std::ranges::random_access_range Pattern>
        requires std::ranges::sized_range<Text> && std::ranges::sized_range<Pattern> &&
                 std::equality_comparable_with<std::ranges::range_reference_t<Text>, std::ranges::range_reference_t<Pattern>>
    static std::vector<int> search(const Text& text, const Pattern& pattern) {
        std::vector<int> result;
        if (std::ranges::empty(pattern)) return result;

        std::vector<int> mp = build_mp(pattern);
        const int n = static_cast<int>(std::ranges::size(text));
        const int m = static_cast<int>(std::ranges::size(pattern));
        int j = 0;

        for (int i = 0; i < n; i++) {
            while (j >= 0 && text[i] != pattern[j])
                j = mp[j];
            j++;
            if (j == m) {
                result.push_back(i - m + 1);
                j = mp[j];
            }
        }
        return result;
    }

    template <std::ranges::random_access_range Text, std::ranges::random_access_range Pattern>
        requires std::ranges::sized_range<Text> && std::ranges::sized_range<Pattern> &&
                 std::equality_comparable_with<std::ranges::range_reference_t<Text>, std::ranges::range_reference_t<Pattern>>
    static std::vector<int> search_non_overlapping(const Text& text, const Pattern& pattern) {
        std::vector<int> result;
        if (std::ranges::empty(pattern)) return result;

        std::vector<int> mp = build_mp(pattern);
        const int n = static_cast<int>(std::ranges::size(text));
        const int m = static_cast<int>(std::ranges::size(pattern));
        int j = 0;

        for (int i = 0; i < n; i++) {
            while (j >= 0 && text[i] != pattern[j])
                j = mp[j];
            j++;
            if (j == m) {
                result.push_back(i - m + 1);
                j = 0;
            }
        }
        return result;
    }

    template <std::ranges::random_access_range Text, std::ranges::random_access_range Pattern>
        requires std::ranges::sized_range<Text> && std::ranges::sized_range<Pattern> &&
                 std::equality_comparable_with<std::ranges::range_reference_t<Text>, std::ranges::range_reference_t<Pattern>>
    static std::vector<int> find_all(const Text& text, const Pattern& pattern) {
        return search(text, pattern);
    }
};

void solve() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    string S;
    read(N, S);
    int ans = 0;
    string&& tmp = S.substr(N - 5, N);
    string HAPPY = "HAPPY";
    for (auto&& [a, b] : ranges::views::zip(tmp, HAPPY)) {
        ans += a != b;
    }
    S[N - 5] = '#';
    vector<int> res = KMP::search(S, HAPPY);
    println("{}", ans + ssize(res));
}

int main() {
    solve();
}