ABC272-G Yet Another mod M
(Test/Manual/abc272_g.test.cpp)

• View this file on GitHub
• Last update: 2024-02-06 11:57:20+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://atcoder.jp/contests/abc272/submissions/50049939

$A$ にもともと過半数を占める要素が存在する場合、任意の $3$ 以上の整数が条件を満たす。

そうで無いとき、適切に $M$ を取ることで $A$ 内の相異なる $2$ 要素以上を操作によって等しくする必要がある。

そのような $M$ は $|A_{i} - A_{j}|$ の約数に限られる。 ( $A_{i}$ と $A_{j}$ は相異なるとする )

なぜなら $A_{i} \equiv A_{j} \pmod{M}\ \to\ A_{i} - A_{j} \equiv 0\pmod{M}$ だからである。

このような $M$ の候補は $O(N^{2}\log (\max A))$ 個ある。この候補をさらに絞ることを考える。

列を円環とみなす。すなわち $i$ 番目の要素と $(i + 1)\pmod{N}$ 番目の要素が隣り合っているとする。

この円環に過半数を占める要素が存在する場合、隣合う $2$ つの要素がその過半数を占める要素であるような位置が必ず存在する。 <- これ天才

以上より、 $|A_{i} - A_{i + 1}|$ の約数のみを調べればよく、 $M$ の候補は $O(N\log (\max A))$ 個となった。

Boyer-Moore majority vote algorithmのverifyの為にライブラリに収録したが、解法の方が興味深い…

Depends on

• 約数列挙 (Src/Number/Divisor.hpp)
• Boyer-MooreのMajority vote algorithm (Src/Sequence/MajorityVote.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Code

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

/*
 * AtCoder Beginner Contest 272-G Yer Another mod M
 * https://atcoder.jp/contests/abc272/submissions/50049939
 */

#include "../../Src/Number/Divisor.hpp"
#include "../../Src/Sequence/MajorityVote.hpp"

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

int solve() {
    using namespace zawa;
    int n; std::cin >> n;
    std::vector<int> a(n);
    for (auto& x : a) std::cin >> x;
    std::sort(a.begin(), a.end());
    std::vector<int> mod;
    for (int i{} ; i < n ; i++) {
        for (int x : Divisor(std::abs(a[i] - a[(i + 1) % n]))) {
            if (x < 3) continue;
            mod.push_back(x);
        }
    }
    std::sort(mod.begin(), mod.end());
    auto m{std::distance(mod.begin(), std::unique(mod.begin(), mod.end()))};
    for (std::ptrdiff_t i{} ; i < m ; i++) {
        std::vector<int> b(n);
        for (int j{} ; j < n ; j++) b[j] = a[j] % mod[i];
        if (MajorityVote<int>(b.begin(), b.end())) {
            return mod[i];
        }
    }
    return -1;
}

int main() {
#ifdef ATCODER
    std::cout << solve() << '\n';
#else
    std::cout << "Hello World" << '\n';
#endif
}

#line 1 "Test/Manual/abc272_g.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * AtCoder Beginner Contest 272-G Yer Another mod M
 * https://atcoder.jp/contests/abc272/submissions/50049939
 */

#line 2 "Src/Number/Divisor.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 4 "Src/Number/Divisor.hpp"

#include <cassert>
#include <type_traits>
#include <vector>

namespace zawa {

// @remark: 約数はソートされていない
template <class T>
std::vector<T> Divisor(T v) {
    assert(v > static_cast<T>(0));
    std::vector<T> res;
    for (T i{1} ; i * i <= v ; i++) {
        if (v % i) continue;
        res.emplace_back(i);
        if (i * i != v) {
            res.emplace_back(v / i);
        }
    }
    return res;
}

} // namespace zawa
#line 2 "Src/Sequence/MajorityVote.hpp"

#line 4 "Src/Sequence/MajorityVote.hpp"

#include <algorithm>
#line 7 "Src/Sequence/MajorityVote.hpp"
#include <optional>
#line 9 "Src/Sequence/MajorityVote.hpp"

namespace zawa {

template <class T, class InputIterator>
std::optional<T> MajorityVote(InputIterator first, InputIterator last) {
    static_assert(std::is_convertible_v<decltype(*first), T>, "InputIterator must be convertible T");
    assert(first != last);
    std::optional<T> remain{}; 
    usize number{};
    for (auto it{first} ; it != last ; it++) {
        if (number) {
            if (remain.value() == *it) {
                number++;
            }
            else {
                number--;
            }
        }
        else {
            remain = *it;
            number++;
        }
    }
    if (number and 2u * std::count(first, last, remain.value()) > std::distance(first, last)) {
        return remain;
    }
    else {
        return std::nullopt;
    }
}

} // namespace zawa
#line 10 "Test/Manual/abc272_g.test.cpp"

#line 12 "Test/Manual/abc272_g.test.cpp"
#include <iostream>
#include <iterator>
#line 15 "Test/Manual/abc272_g.test.cpp"

int solve() {
    using namespace zawa;
    int n; std::cin >> n;
    std::vector<int> a(n);
    for (auto& x : a) std::cin >> x;
    std::sort(a.begin(), a.end());
    std::vector<int> mod;
    for (int i{} ; i < n ; i++) {
        for (int x : Divisor(std::abs(a[i] - a[(i + 1) % n]))) {
            if (x < 3) continue;
            mod.push_back(x);
        }
    }
    std::sort(mod.begin(), mod.end());
    auto m{std::distance(mod.begin(), std::unique(mod.begin(), mod.end()))};
    for (std::ptrdiff_t i{} ; i < m ; i++) {
        std::vector<int> b(n);
        for (int j{} ; j < n ; j++) b[j] = a[j] % mod[i];
        if (MajorityVote<int>(b.begin(), b.end())) {
            return mod[i];
        }
    }
    return -1;
}

int main() {
#ifdef ATCODER
    std::cout << solve() << '\n';
#else
    std::cout << "Hello World" << '\n';
#endif
}

Back to top page