Test/AtCoder/abc398_f.test.cpp

• View this file on GitHub
• Last update: 2025-07-09 19:40:54+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://atcoder.jp/contests/abc398/submissions/67450075
• Link: https://atcoder.jp/contests/abc398/tasks/abc398_f

Depends on

• Manacher (Enumerate Palindromes) (Src/Sequence/Manacher.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Code

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

/*
 * AtCoder Beginner Contest 398 F - ABCBA
 * https://atcoder.jp/contests/abc398/submissions/67450075
 */

#include "../../Src/Sequence/Manacher.hpp"

#include <cassert>
#include <iostream>
#include <string>

int main() {
#ifdef ATCODER
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::string S;
    std::cin >> S;
    const auto D = zawa::Manacher<int>(S);
    int id = -1, ans = 2 * std::ssize(S);
    for (int i = 0 ; i < std::ssize(D) ; i++) {
        const int half = D[i] / 2;
        if ((i / 2) + half == std::ssize(S) - 1) {
            const int len = D[i] + 2 * (std::ssize(S) - D[i]);
            if (ans > len) {
                id = i;
                ans = len;
            }
        }
    }
    assert(id != -1);
    std::string T = S;
    for (int i = (id / 2) - (D[id] + 1) / 2 ; i >= 0 ; i--) T += S[i];
    std::cout << T << '\n';
#else
    std::cout << "Hello World\n";
#endif
}

#line 1 "Test/AtCoder/abc398_f.test.cpp"
// #define PROBLEM "https://atcoder.jp/contests/abc398/tasks/abc398_f"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * AtCoder Beginner Contest 398 F - ABCBA
 * https://atcoder.jp/contests/abc398/submissions/67450075
 */

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

#include <concepts>
#include <optional>
#include <vector>
#include <string>

#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 9 "Src/Sequence/Manacher.hpp"

namespace zawa {

namespace concepts {

template <class C, class T>
concept Container = requires (C c, usize idx) {
    { c[idx] } -> std::convertible_to<T>;
};

} // namespace concepts

namespace internal {

// ref: https://snuke.hatenablog.com/entry/2014/12/02/235837
template <std::equality_comparable T, std::integral RES>
std::vector<RES> Manacher(const std::vector<std::optional<T>>& a) {
    std::vector<RES> res(a.size());
    for (usize i = 0, j = 0 ; i < a.size() ; ) {
        // i + jはここでしか増加せず、i + jは高々|a|しか増えない
        // -> このループは高々|a|
        while (i >= j and i + j < a.size() and a[i - j] == a[i + j]) j++;
        res[i] = j;
        usize k = 1;
        // iは高々|a|までしか増えない->kを増やしているこのループは丁度|a|
        for ( ; i >= k and k + res[i - k] < j ; k++) res[i + k] = res[i - k];
        i += k;
        j -= k;
    } 
    for (usize i = 0 ; i < res.size() ; i++) {
        if (i & 1) {
            res[i] = res[i] & (res[i] ^ 1);
        }
        else {
            res[i] = (res[i] & 1 ? res[i] : res[i] - 1);
        }
    }
    return res;
}

} // namespace internal

template <std::integral RES = usize, std::equality_comparable T = char, class C = std::string>
requires concepts::Container<C, T>
std::vector<RES> Manacher(C a) {
    if (a.empty()) return {};
    std::vector<std::optional<T>> seq(2 * a.size() - 1);
    for (usize i = 0 ; i < a.size() ; i++) {
        seq[2 * i] = std::optional{std::move(a[i])};
    }
    return internal::Manacher<T, RES>(seq);
}

} // namespace zawa
#line 10 "Test/AtCoder/abc398_f.test.cpp"

#include <cassert>
#include <iostream>
#line 14 "Test/AtCoder/abc398_f.test.cpp"

int main() {
#ifdef ATCODER
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::string S;
    std::cin >> S;
    const auto D = zawa::Manacher<int>(S);
    int id = -1, ans = 2 * std::ssize(S);
    for (int i = 0 ; i < std::ssize(D) ; i++) {
        const int half = D[i] / 2;
        if ((i / 2) + half == std::ssize(S) - 1) {
            const int len = D[i] + 2 * (std::ssize(S) - D[i]);
            if (ans > len) {
                id = i;
                ans = len;
            }
        }
    }
    assert(id != -1);
    std::string T = S;
    for (int i = (id / 2) - (D[id] + 1) / 2 ; i >= 0 ; i--) T += S[i];
    std::cout << T << '\n';
#else
    std::cout << "Hello World\n";
#endif
}

Back to top page