ABC193-F Zebraness
(Test/AtCoder/abc193_f.test.cpp)

• View this file on GitHub
• Last update: 2024-02-01 12:13:59+09:00
• Problem: https://atcoder.jp/contests/abc193/tasks/abc193_f

燃やす埋める。

$f: \{ 0, 1 \}^{n^{2}}\ \to\ \mathbb{Z}$

$f$ の定義域: 長さ $n^{2}$ の01列全体

• マス $(i, j)$ の色を列の要素に対応させる
• 例えば、 $(n = 5)$ 「マス $(2, 3)$ が黒色」を表現したいなら「列の $2\times 5 + 3 = 13$ 番目の要素を $1$ にする」など

$f$ の値域: 整数全体

• しまうま度を意味する
• 入力とは矛盾したグリッドの状態(に対応した列)を引数にとった時は、 $-\infty$ を返すこととする

このように $f$ を上手く表現することができるならば、 $f$ を最大化する問題に帰着することができる。

• よくある賞金・罰金の考え方に思いをはせると割と自然に表現できる
• ?じゃないマスに矛盾した色を割り当てる状態ならば(Wなのに黒を割り当てたとか…) $-\infty$ 、そうでなければ $+0$
• 隣合うマスに異なる色を割り当てたら $+1$

最小カットに帰着させたいので、全ての賞金・罰金を $-1$ 倍する。すると困ったことに劣モジュラでなくなる。困ります。

そこで、「隣合うマスに異なる色を割り当てたら $+1$ (現在は $-1$ 倍しているので $-1$ )」に注目する。グリッドグラフ上で $4$ 近傍で隣合う関係は二部グラフをなす。

マス $(i, j)$ の色を $(i + j)$ が偶数なら白黒の割り当てを反転する。-> 「隣合うマスに異なる色を割り当てたら $-1$ 」が「隣合うマスに同じ色を割り当てたら $-1$ 」になる

劣モジュラ性を持つようになりました。goodgoodgood

全体を $-1$ 倍しているので、BurnBuryが返す値は最適解の $-1$ 倍であることに注意

Depends on

• Src/Graph/Flow/BurnBury.hpp
• Dinic (最大流・最小カット) (Src/Graph/Flow/Dinic.hpp)
• ioまわりの設定 (Src/Template/IOSetting.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)
• Src/Utility/U32Pair.hpp

Code

#define PROBLEM "https://atcoder.jp/contests/abc193/tasks/abc193_f"

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/Graph/Flow/BurnBury.hpp"

int main() {
    using namespace zawa;
    SetFastIO();

    int n; std::cin >> n;
    std::vector s(n, std::string{});
    for (auto& v : s) std::cin >> v;

    auto f{[&](int x, int y) -> int {
        return x * n + y;
    }};
    const int dx[4]{ 1, 0, -1, 0 };
    const int dy[4]{ 0, 1, 0, -1 };
    auto in{[&](int x, int y) -> bool {
        return 0 <= x and x < n and 0 <= y and y < n;
    }};

    BurnBury<int> optimizer(n * n);
    const int INF{(int)1e5};
    for (int x{} ; x < n ; x++) {
        for (int y{} ; y < n ; y++) {
            if ((x + y) % 2 == 0) {
                optimizer.func1(f(x, y), {
                        (s[x][y] == 'W' ? INF : 0),
                        (s[x][y] == 'B' ? INF : 0)
                        });
            }
            else {
                optimizer.func1(f(x, y), {
                        (s[x][y] == 'B' ? INF : 0),
                        (s[x][y] == 'W' ? INF : 0)
                        });
            }
            for (int d{} ; d < 4 ; d++) {
                int nx{x + dx[d]}, ny{y + dy[d]};
                if (!in(nx, ny)) continue;
                if (f(x, y) > f(nx, ny)) continue;
                optimizer.func2(f(x, y), f(nx, ny), {-1, 0, 0, -1});
            }
        }
    }

    int ans{optimizer.build()};  
    ans *= -1;
    std::cout << ans << '\n';
}

#line 1 "Test/AtCoder/abc193_f.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc193/tasks/abc193_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/Graph/Flow/BurnBury.hpp"

#line 2 "Src/Utility/U32Pair.hpp"

#line 4 "Src/Utility/U32Pair.hpp"

#include <functional>
#line 7 "Src/Utility/U32Pair.hpp"

namespace zawa {

class U32Pair {
private:
    static constexpr u32 SHIFT{32};
    static constexpr u32 MASK{static_cast<u32>((1LL << SHIFT) - 1)};
    u64 value_{};
public:
    constexpr U32Pair() {}
    constexpr U32Pair(u32 first, u32 second) {
        value_ = (static_cast<u64>(first) << SHIFT) | second;
    }
    constexpr u32 first() const noexcept {
        return static_cast<u32>(value_ >> SHIFT);
    }
    constexpr u32 second() const noexcept {
        return static_cast<u32>(value_ & MASK);
    }
    constexpr u64 combined() const noexcept {
        return value_;
    }
    constexpr U32Pair& operator=(const U32Pair& rhs) {
        value_ = rhs.value_;
        return *this;
    }
    friend constexpr bool operator==(const U32Pair& lhs, const U32Pair& rhs) {
        return lhs.value_ == rhs.value_;
    }
    friend constexpr bool operator!=(const U32Pair& lhs, const U32Pair& rhs) {
        return lhs.value_ != rhs.value_;
    }
    friend constexpr bool operator<(const U32Pair& lhs, const U32Pair& rhs) {
        return lhs.value_ < rhs.value_;
    }
    friend constexpr bool operator<=(const U32Pair& lhs, const U32Pair& rhs) {
        return lhs.value_ <= rhs.value_;
    }
    friend constexpr bool operator>(const U32Pair& lhs, const U32Pair& rhs) {
        return lhs.value_ > rhs.value_;
    }
    friend constexpr bool operator>=(const U32Pair& lhs, const U32Pair& rhs) {
        return lhs.value_ >= rhs.value_;
    }
    friend std::ostream& operator<<(std::ostream& os, const U32Pair& pair) {
        os << '(' << pair.first() << ',' << pair.second() << ')';
        return os;
    }
};

struct U32PairHash {
    usize operator()(const U32Pair& pair) const noexcept {
        return std::hash<u64>{}(pair.combined());
    }
};

} // namespace zawa
#line 2 "Src/Graph/Flow/Dinic.hpp"

#line 5 "Src/Graph/Flow/Dinic.hpp"

#include <algorithm>
#include <cassert>
#include <limits>
#include <type_traits>
#include <vector>
#include <queue>

namespace zawa {

template <class Cap> 
class Dinic {
private:
    static_assert(std::is_signed_v<Cap>, "Cap must be signed");
    usize n_{}, m_{};
    static constexpr u32 invalid() noexcept {
        return std::numeric_limits<u32>::max();
    }
public:
    inline usize size() const noexcept {
        return n_;
    }
    inline usize edgeNumber() const noexcept {
        return m_;
    }
private:
    struct Edge {
        u32 to{}, rev{};
        Cap residual{};
        Edge() = default;
        Edge(u32 to, u32 rev, const Cap& residual) 
            : to{to}, rev{rev}, residual{residual} {}
    };

    std::vector<std::vector<Edge>> g_;
    std::vector<U32Pair> edges_;
    std::vector<u32> label_, cur_;

    bool dualStep(u32 s, u32 t) {
        std::fill(label_.begin(), label_.end(), invalid());
        label_[s] = 0;
        std::queue<u32> queue{ { s } };
        while (queue.size()) {
            u32 v{queue.front()};
            queue.pop();
            for (const Edge& e : g_[v]) if (e.residual > 0) {
                if (label_[e.to] > label_[v] + 1) {
                    label_[e.to] = label_[v] + 1;
                    if (e.to == t) return true;
                    queue.emplace(e.to);
                }
            }
        }
        return false;
    }

    bool admissible(u32 v, const Edge& e) const noexcept {
        return e.residual > 0 and label_[v] + 1 == label_[e.to];
    }

    inline void flow(Edge& e, Cap f) {
        e.residual -= f;
        g_[e.to][e.rev].residual += f;
    }

    Cap dfs(u32 v, u32 t, Cap up) {
        if (v == t) return up;
        Cap res{};
        for (u32& i{cur_[v]} ; i < g_[v].size() ; i++) {
            if (!admissible(v, g_[v][i])) continue;
            Cap f{dfs(g_[v][i].to, t, std::min(g_[v][i].residual, up - res))};
            if (f == 0) continue;
            flow(g_[v][i], f);
            res += f;
            if (res == up) return res;
        }
        return res;
    }

    Cap primalStep(u32 s, u32 t) {
        std::fill(cur_.begin(), cur_.end(), 0u);
        cur_[t] = g_[t].size();
        Cap res{};
        while (true) {
            Cap f{dfs(s, t, std::numeric_limits<Cap>::max())};
            if (f == 0) break;
            res += f;
        }
        return res;
    }

    const Edge& edge(u32 i) const noexcept {
        return g_[edges_[i].first()][edges_[i].second()];
    }
    const Edge& reverse(u32 i) const noexcept {
        const Edge& e{edge(i)};
        return g_[e.to][e.rev];
    }

public:
    Dinic() = default;
    Dinic(u32 n, u32 m = 0u) 
        : n_{n}, m_{m}, g_(n), edges_{}, label_(n), cur_(n) {
        g_.shrink_to_fit();
        label_.shrink_to_fit();
        cur_.shrink_to_fit();
        edges_.reserve(m);
    }

    u32 addEdge(u32 u, u32 v, const Cap& cap) {
        assert(u < size());
        assert(v < size());
        u32 id{static_cast<u32>(g_[u].size())};
        u32 revId{u == v ? id + 1 : static_cast<u32>(g_[v].size())};
        u32 res{static_cast<u32>(edges_.size())};
        edges_.emplace_back(u, id);
        g_[u].emplace_back(v, revId, cap);
        g_[v].emplace_back(u, id, Cap{});
        m_++;
        return res;
    }

    const Cap& flowed(u32 id) const noexcept {
        assert(id < edgeNumber());
        return reverse(id).residual;
    }
    const Cap& residual(u32 id) const noexcept {
        assert(id < edgeNumber());
        return edge(id).residual;
    }
    const Cap& capacity(u32 id) const noexcept {
        assert(id < edgeNumber());
        return edge(id).residual + reverse(id).residual;
    }
    const u32& from(u32 id) const noexcept {
        assert(id < edgeNumber());
        return edges_[id].first();
    }
    const u32& to(u32 id) const noexcept {
        assert(id < edgeNumber());
        return edge(id).to;
    }

    Cap flow(u32 s, u32 t) {
        assert(s < size());
        assert(t < size()); 
        Cap res{};
        while (dualStep(s, t)) {
            res += primalStep(s, t);
        }
        return res;
    }

    std::vector<bool> cut(u32 s) {
        std::vector<bool> res(size());
        res[s] = true;
        std::queue<u32> queue{ { s } };
        while (queue.size()) {
            u32 v{queue.front()};
            queue.pop();
            for (const auto& e : g_[v]) if (e.residual > 0 and !res[e.to]) {
                res[e.to] = true;
                queue.emplace(e.to);
            }
        }
        return res;
    }    
};

} // namespace zawa
#line 6 "Src/Graph/Flow/BurnBury.hpp"

#line 8 "Src/Graph/Flow/BurnBury.hpp"
#include <unordered_map>
#line 10 "Src/Graph/Flow/BurnBury.hpp"

namespace zawa {

template <class Cost>
class BurnBury {
private:
    usize n_{}, source_{}, sink_{}, graphsize_{};
    Dinic<Cost> mf_{}; 
    Cost common_{};
    std::unordered_map<U32Pair, Cost, U32PairHash> edge_{};
    void addEdge(u32 u, u32 v, const Cost& cost) {
        edge_[U32Pair{ u, v }] += cost;
    }
    constexpr usize size() const noexcept {
        return n_;
    }
public:
    BurnBury() = default;    
    BurnBury(usize n) : n_{n}, source_{n}, sink_{n + 1}, graphsize_{n + 2} {
        assert(n);
    }
    void constant(const Cost& cost) {
        common_ += cost;
    }
    void func1(u32 v, const std::vector<Cost>& cost) {
        assert(v < size());
        assert(cost.size() == (1u << 1));
        if (cost[0] <= cost[1]) {
            addEdge(source_, v, cost[1] - cost[0]);
            constant(cost[0]);
        }
        else {
            addEdge(v, sink_, cost[0] - cost[1]);
            constant(cost[1]);
        }
    }
    void func2(u32 u, u32 v, const std::vector<Cost>& cost) {
        assert(u < size());
        assert(v < size());
        assert(cost.size() == (1u << 2));
        constant(cost[0]);
        func1(u, { Cost{0}, cost[2] - cost[0] });
        func1(v, { Cost{0}, cost[3] - cost[2] });
        assert(cost[1] + cost[2] - cost[0] - cost[3] >= 0);
        addEdge(u, v, cost[1] + cost[2] - cost[0] - cost[3]);
    }
    void func3(u32 u, u32 v, u32 w, const std::vector<Cost>& cost) {
        assert(u < size());
        assert(v < size());
        assert(w < size());
        assert(cost.size() == (1u << 3));
        Cost p{cost[1] + cost[3] + cost[5] + cost[6] - (cost[1] + cost[2] + cost[4] + cost[7])};
        if (p >= 0) {
            constant(cost[0]);
            func1(u, Cost{0}, cost[5] - cost[1]);
            func1(v, Cost{0}, cost[6] - cost[4]);
            func1(w, Cost{0}, cost[3] - cost[2]);
            // 01以外は0
            func2(u, v, { Cost{0}, cost[2] + cost[4] - cost[0] - cost[6], Cost{0}, Cost{0} });
            func2(v, w, { Cost{0}, cost[1] + cost[2] - cost[0] - cost[3], Cost{0}, Cost{0} });
            func2(w, u, { Cost{0}, cost[1] + cost[4] - cost[0] - cost[5], Cost{0}, Cost{0} });
            // 111とすると-p
            addEdge(u, graphsize_, p);
            addEdge(v, graphsize_, p);
            addEdge(w, graphsize_, p);
            addEdge(graphsize_, sink_, p);
            constant(-p);
            graphsize_++;
        }
        else {
            constant(cost[7]);
            func1(u, { cost[2] - cost[6], Cost{0} });
            func1(v, { cost[1] - cost[3], Cost{0} });
            func1(w, { cost[4] - cost[5], Cost{0} });
            // 10の時
            func2(u, v, { Cost{0}, Cost{0}, cost[3] + cost[5] - cost[1] - cost[7], Cost{0} });
            func2(v, w, { Cost{0}, Cost{0}, cost[5] + cost[6] - cost[4] - cost[7], Cost{0} });
            func2(w, u, { Cost{0}, Cost{0}, cost[3] + cost[6] - cost[2] - cost[7], Cost{0} });
            // 000
            addEdge(source_, graphsize_, -p);
            addEdge(graphsize_, u, -p);
            addEdge(graphsize_, v, -p);
            addEdge(graphsize_, w, -p);
            constant(p);
            graphsize_++;
        }
    }

    [[nodiscard]] Cost build() {
        mf_ = Dinic<Cost>(graphsize_);
        for (const auto& [uv, cost] : edge_) {
            mf_.addEdge(uv.first(), uv.second(), cost);
        }
        Cost res{mf_.flow(source_, sink_)};
        res += common_;
        return res;
    }

    [[nodiscard]] std::vector<u32> assign() {
        auto tos{mf_.cut(source_)}, tot{mf_.cut(sink_)};
        std::vector<u32> res(size());
        for (u32 i{} ; i < size() ; i++) {
            if (!tos[i] and !tot[i]) res[i] = 2;
            else if (tos[i]) res[i] = 0;
            else res[i] = 1;
        }
        return res;
    }
};

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

int main() {
    using namespace zawa;
    SetFastIO();

    int n; std::cin >> n;
    std::vector s(n, std::string{});
    for (auto& v : s) std::cin >> v;

    auto f{[&](int x, int y) -> int {
        return x * n + y;
    }};
    const int dx[4]{ 1, 0, -1, 0 };
    const int dy[4]{ 0, 1, 0, -1 };
    auto in{[&](int x, int y) -> bool {
        return 0 <= x and x < n and 0 <= y and y < n;
    }};

    BurnBury<int> optimizer(n * n);
    const int INF{(int)1e5};
    for (int x{} ; x < n ; x++) {
        for (int y{} ; y < n ; y++) {
            if ((x + y) % 2 == 0) {
                optimizer.func1(f(x, y), {
                        (s[x][y] == 'W' ? INF : 0),
                        (s[x][y] == 'B' ? INF : 0)
                        });
            }
            else {
                optimizer.func1(f(x, y), {
                        (s[x][y] == 'B' ? INF : 0),
                        (s[x][y] == 'W' ? INF : 0)
                        });
            }
            for (int d{} ; d < 4 ; d++) {
                int nx{x + dx[d]}, ny{y + dy[d]};
                if (!in(nx, ny)) continue;
                if (f(x, y) > f(nx, ny)) continue;
                optimizer.func2(f(x, y), f(nx, ny), {-1, 0, 0, -1});
            }
        }
    }

    int ans{optimizer.build()};  
    ans *= -1;
    std::cout << ans << '\n';
}

Back to top page