ICPC 2019-2020 North-Western Russia Regional Contest C - Cross-Stitch

前置き

公式解説がロシア語なので、自分の解法を書き留めておきます。

問題

ここ

解法

裏面の縫い目の個数は決まっている (表面の縫い目の個数よりちょうど $1$ だけ少ない) ので、裏面のすべての縫い目の長さを $1$ に出来るならば、明らかにそれが最適。実は、これは常に達成可能である。

$(h+1)\times (w+1)$ 頂点のグラフを考え、各 X に対して下図のように有向辺を張る。ここで、X が偶数行目にあるか、あるいは奇数行目にあるかで辺の張り方が異なることに注意する。

上の図で、すべての頂点において入次数と出次数が等しい。また、制約から、不要な頂点を取り除いたグラフは連結なのでオイラー閉路が存在する。従って、任意のオイラー閉路を一つ選んで裏面の縫い目を一つ取り除くことで所望の解を得る。時間計算量は $O(hw)$。

実装 (C++)

提出リンク

折り畳み

オイラー路を求めるやつを実際に書くのは初めてで、何かを参照したわけでもないので使用実績はこの問題だけです。何が言いたいかというと、他の問題で使うとバグってて大変なことになるかもしれません。

#include <iostream>

#include <algorithm>
#include <cassert>
#include <optional>
#include <vector>

namespace suisen {
    struct DirectedEulerianGraph {
        DirectedEulerianGraph() {}
        DirectedEulerianGraph(int n) : n(n), g(n), in_deg(n, 0) {}

        void add_edge(int u, int v) {
            g[u].push_back(v);
            ++in_deg[v];
        }

        std::optional<std::vector<int>> euler_circuit(int start = 0) {
            std::size_t edge_num = 0;
            std::vector<std::vector<bool>> used(n);
            for (int i = 0; i < n; ++i) {
                const int sz = g[i].size();
                edge_num += sz;
                used[i].resize(sz, false);
                if (in_deg[i] != sz) return std::nullopt;
            }
            std::vector<int> res;
            auto dfs = [&](auto dfs, int u) -> void {
                for (std::size_t i = 0; i < g[u].size(); ++i) {
                    if (used[u][i]) continue;
                    const int v = g[u][i];
                    used[u][i] = true;
                    dfs(dfs, v);
                }
                res.push_back(u);
            };
            dfs(dfs, start);
            std::reverse(res.begin(), res.end());
            if (res.size() != edge_num + 1) return std::nullopt;
            return res;
        }
        std::optional<std::vector<int>> eulerian_trail() {
            int s = -1, t = -1, invalid = -1;
            for (int i = 0; i < n; ++i) {
                int out_deg = g[i].size();
                if (out_deg == in_deg[i] + 1) {
                    (s < 0 ? s : invalid) = i;
                } else if (out_deg == in_deg[i] - 1) {
                    (t < 0 ? t : invalid) = i;
                } else if (out_deg != in_deg[i]) {
                    invalid = i;
                }
            }
            if (s < 0 or t < 0 or invalid >= 0) return std::nullopt;
            add_edge(t, s);
            auto res = *euler_circuit(s);
            res.pop_back();
            // remove edge (t, s)
            g[t].pop_back();
            if (res.back() == t) return res;
            auto is_ts_edge = [&](int u, int v) {
                return u == t and v == s;
            };
            std::rotate(res.begin(), std::adjacent_find(res.begin(), res.end(), is_ts_edge) + 1, res.end());
            return res;
        }
        
        const std::vector<int>& operator[](int u) const {
            return g[u];
        }
    private:
        int n;
        std::vector<std::vector<int>> g;
        std::vector<int> in_deg;
    };
}

using suisen::DirectedEulerianGraph;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int w, h;
    std::cin >> w >> h;
    std::vector<std::string> s(h);
    for (auto &row : s) std::cin >> row;

    DirectedEulerianGraph g((w + 1) * (h + 1));
    auto id = [&](int i, int j) {
        return i * (w + 1) + j;
    };
    int si = -1, sj = -1;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (s[i][j] != 'X') continue;
            if (i & 1) {
                si = i + 1, sj = j;
                g.add_edge(id(i + 1, j + 1), id(i, j));
                g.add_edge(id(i + 1, j), id(i, j + 1));
                g.add_edge(id(i, j), id(i + 1, j));
                g.add_edge(id(i, j + 1), id(i + 1, j + 1));
            } else {
                si = i, sj = j;
                g.add_edge(id(i, j), id(i + 1, j + 1));
                g.add_edge(id(i, j + 1), id(i + 1, j));
                g.add_edge(id(i + 1, j), id(i, j));
                g.add_edge(id(i + 1, j + 1), id(i, j + 1));
            }
        }
    }
    auto ans = *g.euler_circuit(id(si, sj));
    ans.pop_back();
    std::cout << ans.size() - 1 << '\n';
    for (int ij : ans) {
        int i = ij / (w + 1), j = ij % (w + 1);
        std::cout << j << ' ' << i << '\n';
    }
    return 0;
}

感想

明らかに L の方が難しいと思うんだけど、何故かあんまり解かれてなくてバチャ中は見逃してしまった...