ABC396-G Flip Row or Col
(Test/AtCoder/abc396_g.test.cpp)

• View this file on GitHub
• Last update: 2025-06-02 16:41:21+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://atcoder.jp/contests/abc396/submissions/66400307
• Link: https://atcoder.jp/contests/abc396/tasks/abc396_g

$A_{i}$ の $i$ 行目を二進表記の整数だと思うことにする。この整数を $a_{i}$ とする。

解は $\min_{i=0}^{2^W-1}\{\sum_{j = 1}^{H} \min\{\text{popcnt}(a_j \oplus i), W - \text{popcnt}(a_j\oplus i)\}\}$ であるため、これを頑張って早く求めたい。

$a_{j}$ の頻度列を取り $c$ とする。目的の式は $c$ を用いて $\min_{i=0}^{2^W-1}\{\sum_{j = 0}^{2^{W}-1} c_{j}\times \min\{\text{popcnt}(j \oplus i), W - \text{popcnt}(j\oplus i)\}\}$ と表せる。

xor畳み込みの形になっているので、OK

Depends on

• Bitwise XOR Convolution (Src/Sequence/BitwiseXORConvolution.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Code

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

/*
 * AtCoder Beginner Contest 396 - G Flip Row or Col
 * https://atcoder.jp/contests/abc396/submissions/66400307
 */

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

#include <algorithm>
#include <bit>
#include <iostream>
#include <string>
#include <vector>
#include <ranges>

int main() {
#ifdef ATCODER
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int H, W;
    std::cin >> H >> W;
    std::vector<int> A(1 << W), B(1 << W);
    for (int i = 0 ; i < H ; i++) {
        std::string S;
        std::cin >> S;
        int v = 0;
        for (int j = 0 ; j < W ; j++) if (S[j] == '1') v |= 1 << j;
        A[v]++;
    }
    for (int i = 0 ; i < (1 << W) ; i++) {
        const int cnt = std::popcount((unsigned)i);
        B[i] = std::min(cnt, W - cnt);
    }
    auto C = zawa::BitwiseXORConvolution<long long>(A, B);
    std::cout << *std::ranges::min_element(C) << '\n';
#else
    std::cout << "Hello World\n";
#endif
}

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

/*
 * AtCoder Beginner Contest 396 - G Flip Row or Col
 * https://atcoder.jp/contests/abc396/submissions/66400307
 */

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

#include <bit>
#include <concepts>
#include <cassert>
#include <vector>

namespace zawa {

// note: 返り値の各点の値は真の値より(2^{k/2})倍されている
template <class T>
void FastWalshHadamardTransform(std::vector<T>& A) {
    if (A.empty()) return;
    while (!std::has_single_bit(A.size())) A.push_back(T{0});
    const usize k = std::bit_width(A.size()) - 1, n = A.size();
    for (usize i = 0 ; i < k ; i++) {
        const usize bit = 1 << i;
        for (usize j = 0 ; j < n ; j += bit << 1) {
            for (usize k = 0 ; k < bit ; k++) {
                const T p = A[j + k], q = A[j + k + bit];
                A[j + k] = p + q;
                A[j + k + bit] = p - q;
            }
        }
    }
}

template <class T>
std::vector<T> BitwiseXORConvolution(std::vector<T> A, std::vector<T> B) {
    FastWalshHadamardTransform(A);
    FastWalshHadamardTransform(B);
    if (A.size() > B.size()) std::swap(A, B);
    for (usize i = 0 ; i < A.size() ; i++) A[i] *= B[i];
    FastWalshHadamardTransform(A);
    if (A.empty()) return A;
    assert(std::has_single_bit(A.size()));
    if constexpr (std::integral<T>) {
        const usize d = std::bit_width(A.size()) - 1;
        for (auto& a : A) a >>= d;
    }
    else {
        const T d = [&]() {
            assert(std::has_single_bit(A.size()));
            usize exp = std::bit_width(A.size()) - 1;
            T v = T{1} / T{2}, res = T{1};
            while (exp) {
                if (exp & 1) res = res * v;
                v = v * v;
                exp >>= 1;
            }
            return res;
        }();
        for (T& a : A) a *= d;
    }
    return A;
}

template <class T, class U>
requires (!std::same_as<T, U> and std::convertible_to<U, T>)
std::vector<T> BitwiseXORConvolution(std::vector<U> A, std::vector<U> B) {
    std::vector<T> a(A.size()), b(B.size());
    for (usize i = 0 ; i < A.size() ; i++) a[i] = static_cast<T>(std::move(A[i]));
    for (usize i = 0 ; i < B.size() ; i++) b[i] = static_cast<T>(std::move(B[i]));
    return BitwiseXORConvolution<T>(a, b);
}

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

#include <algorithm>
#line 13 "Test/AtCoder/abc396_g.test.cpp"
#include <iostream>
#include <string>
#line 16 "Test/AtCoder/abc396_g.test.cpp"
#include <ranges>

int main() {
#ifdef ATCODER
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int H, W;
    std::cin >> H >> W;
    std::vector<int> A(1 << W), B(1 << W);
    for (int i = 0 ; i < H ; i++) {
        std::string S;
        std::cin >> S;
        int v = 0;
        for (int j = 0 ; j < W ; j++) if (S[j] == '1') v |= 1 << j;
        A[v]++;
    }
    for (int i = 0 ; i < (1 << W) ; i++) {
        const int cnt = std::popcount((unsigned)i);
        B[i] = std::min(cnt, W - cnt);
    }
    auto C = zawa::BitwiseXORConvolution<long long>(A, B);
    std::cout << *std::ranges::min_element(C) << '\n';
#else
    std::cout << "Hello World\n";
#endif
}

Back to top page