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: ABC296-F Simultaneous Swap (互換は奇数回の隣接swap)
(Test/AtCoder/abc296_f.test.cpp)

長さ $N$ の数列 $A = (A_{1}, A_{2}, \dots, A_{N})$ の $L$ 番目の要素と $R$ 番目の要素をswapすることを考える。

これは $2(R - L - 1) + 1$ 回の隣接要素のswapで実現できる。

$A_{L}$ の要素を $A_{R}$ のところに運ぶのに $R - L$ 回のswap、現在 $A_{R}$ は $R - 1$ 番目にいて、これを $L$ 番目に運ぶのに $R - L - 1$ 回のswapを要する。

$2\times$ 整数 $+1$ の形で表現できる整数は奇数であることを思い出すと、以下が成り立つことがわかる。

順列は互換( $L$ 番目の要素と $R$ 番目の要素をswapする)によって転倒数の偶奇が必ず入れ替わる


この事実を利用してこの問題を解くことができる。

$A, B$ が多重集合として一致していることを仮定する。

$A$ がdistinctのとき

操作によって $A$ の転倒数の偶奇、 $B$ の転倒数の偶奇は必ず入れ替わる。すなわち $A$ の転倒数 - $B$ の転倒数の偶奇は不変である。

よって $A$ の転倒数の偶奇と $B$ の転倒数の偶奇が一致していることが必要だが、実は十分条件にもなっている。実際に操作列を構築することで示せるようだ。

$A$ がdistinctでないとき

うまく $(i, j, k)$ を選ぶことで転倒数の偶奇すらずらせる。常にYes

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc296/tasks/abc296_f"

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/Sequence/InversionNumber.hpp"

#include <iostream>
#include <vector>

using namespace zawa;

int main() {
    SetFastIO();
    int N;
    std::cin >> N;
    std::vector<int> A(N), B(N);
    for (auto& x : A) {
        std::cin >> x;
        x--;
    }
    for (auto& x : B) {
        std::cin >> x;
        x--;
    }
    // 多重集合として一致しているか？
    std::vector<int> cnt(N);
    for (auto x : A) cnt[x]++;
    for (auto x : B) cnt[x]--;
    for (int i{} ; i < N ; i++) if (cnt[i]) {
        std::cout << "No" << '\n';
        return 0;
    }
    // 同じ要素が含まれているか？
    for (auto x : A) cnt[x]++;
    for (int i{} ; i < N ; i++) if (cnt[i] > 1) {
        std::cout << "Yes" << '\n';
        return 0;
    }
    // 転倒数の偶奇
    bool ans{InversionParity(A.begin(), A.end()) == InversionParity(B.begin(), B.end())};
    std::cout << (ans ? "Yes" : "No") << '\n';
}
#line 1 "Test/AtCoder/abc296_f.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc296/tasks/abc296_f"

#line 2 "Src/Template/IOSetting.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/Template/IOSetting.hpp"

#include <iostream>
#include <iomanip>

namespace zawa {

void SetFastIO() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
}

void SetPrecision(u32 dig) {
    std::cout << std::fixed << std::setprecision(dig);
}

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

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

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

namespace zawa {

template <class InputIterator>
u64 InversionNumber(InputIterator first, InputIterator last) {
    assert((usize)std::distance(first, last) >= usize{0});
    std::vector<std::remove_reference_t<decltype(*first)>> A(first, last);
    auto rec{[&](auto rec, usize L, usize R) -> u64 {
        if (R - L <= usize{1}) return 0; 
        usize M{(L + R) >> 1};
        u64 res{rec(rec, L, M) + rec(rec, M, R)};
        std::vector<u64> tmp(R - L);
        usize i{L}, j{M}, k{};
        while (i < M and j < R) {
            if (A[i] <= A[j]) {
                tmp[k++] = A[i++];
            }
            else {
                res += M - i;
                tmp[k++] = A[j++];
            }
        }
        while (i < M) tmp[k++] = A[i++];
        while (j < R) tmp[k++] = A[j++];
        for (usize l{L} ; l < R ; l++) {
            A[l] = tmp[l - L];
        }
        return res;
    }};
    return rec(rec, usize{0}, usize{A.size()});
}

template <class InputIterator>
bool InversionParity(InputIterator first, InputIterator last) {
    assert((usize)std::distance(first, last) >= usize{0});
    std::vector<std::remove_reference_t<decltype(*first)>> A(first, last);
    auto rec{[&](auto rec, usize L, usize R) -> bool {
        if (R - L <= usize{1}) return 0; 
        usize M{(L + R) >> 1};
        bool res{rec(rec, L, M) != rec(rec, M, R)};
        std::vector<u64> tmp(R - L);
        usize i{L}, j{M}, k{};
        while (i < M and j < R) {
            if (A[i] <= A[j]) {
                tmp[k++] = A[i++];
            }
            else {
                res ^= (M - i) & 1;
                tmp[k++] = A[j++];
            }
        }
        while (i < M) tmp[k++] = A[i++];
        while (j < R) tmp[k++] = A[j++];
        for (usize l{L} ; l < R ; l++) {
            A[l] = tmp[l - L];
        }
        return res;
    }};
    return rec(rec, usize{0}, usize{A.size()});
}

} // namespace zawa
#line 5 "Test/AtCoder/abc296_f.test.cpp"

#line 8 "Test/AtCoder/abc296_f.test.cpp"

using namespace zawa;

int main() {
    SetFastIO();
    int N;
    std::cin >> N;
    std::vector<int> A(N), B(N);
    for (auto& x : A) {
        std::cin >> x;
        x--;
    }
    for (auto& x : B) {
        std::cin >> x;
        x--;
    }
    // 多重集合として一致しているか？
    std::vector<int> cnt(N);
    for (auto x : A) cnt[x]++;
    for (auto x : B) cnt[x]--;
    for (int i{} ; i < N ; i++) if (cnt[i]) {
        std::cout << "No" << '\n';
        return 0;
    }
    // 同じ要素が含まれているか？
    for (auto x : A) cnt[x]++;
    for (int i{} ; i < N ; i++) if (cnt[i] > 1) {
        std::cout << "Yes" << '\n';
        return 0;
    }
    // 転倒数の偶奇
    bool ans{InversionParity(A.begin(), A.end()) == InversionParity(B.begin(), B.end())};
    std::cout << (ans ? "Yes" : "No") << '\n';
}
Back to top page