2023-09-17

AtCoder ABC 320 G - Slot Strategy 2 (Hard) (橙色, 600 点)

AtCoder AtCoder600点 ABC-G 橙色diff フローグラフテク:26文字のアルファベット文字を個別に考える個別の要素の動きに注目する二分探索最大流問題マッチング二部マッチング二次元グリッド被覆最小包含・最小被覆を求める割当問題スロットを題材とした問題最大値の最小化二分探索:最大値の最小化中堅以上の典型要素を詰め合わせた教育的問題テク:幅が小さいことに着目する(O(WH)がO(W^2)になる) テク:文字の種類数が少ない

広く捉えれば「各スロットに対して止める秒数を割り当てる」方法を考える割当問題だと言えそう。

問題へのリンク

問題概要

$N \times M$ のグリッド $S$ が与えられる。各マスには 0 から 9 までの数字が描かれている。

今、次の条件を満たす 0 以上の整数値 $k_{0}, k_{1}, \dots, k_{N-1}$ を考えたとき、 $\min(k_{0}, k_{1}, \dots, k_{N-1})$ の最小値を求めよ。

$k_{i}$ を $M$ で割った余りを $r_{i}$ としたとき
$S_{0, r_{0}}, S_{1, r_{1}}, \dots, S_{N-1, r_{N-1}}$ の値が等しい

(スロットを題材とした問題)

制約

$1 \le N \le 100$
$1 \le M \le 10000$

解法メモ

揃う数値が 0〜9 しかないので、10 通り考えることにする。さらに、答えを $x$ 以下にできるかどうかを判定する問題を解いて、二分探索法で求めることにする。

このとき、次のようにフローネットワークを作り、流量 $N$ のフローを流せれば Yes、流せなければ No と判定すればよい。

左側頂点 $i$ ：行 $i$ に対応する、ソースから頂点 $i$ へ流量 1 の辺を張る
右側頂点 $j$ ：列 $j$ に対応する、頂点 $j$ からシンクへ流量 (0 以上 $x$ 以下の整数のうち $M$ で割った余りが $j$ であるものの個数) の辺を張る
左側頂点 $i$ から、右側頂点 $j$ へ、 $S_{i, j}$ が考えている値に一致している場合のみ、流量 1 の辺を張る

ただし、このままでは TLE してしまう。各行について、考えている数値が登場する添字を小さい順に $N$ 個まで考えればよい。

これをすることで、フローネットワークの辺数が $O(N^{2})$ となるので、フローを流したときの計算量は $O(N(N^{2}+M)$ となる (頂点を座標圧縮をすれば $O(N^{3})$ にもなる)。

グリッドに書かれた数値の種類数を $D$ とすると、全体の計算量は $O(NM + D(N^{3} + NM)(\log N + \log M))$ となる。

コード

#include<bits/stdc++.h>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

// edge class (for network-flow)
template<class FLOWTYPE> struct FlowEdge {
    // core members
    int rev, from, to;
    FLOWTYPE cap, icap, flow;
    
    // constructor
    FlowEdge(int r, int f, int t, FLOWTYPE c)
    : rev(r), from(f), to(t), cap(c), icap(c), flow(0) {}
    void reset() { cap = icap, flow = 0; }
    
    // debug
    friend ostream& operator << (ostream& s, const FlowEdge& E) {
        return s << E.from << "->" << E.to << '(' << E.flow << '/' << E.icap << ')';
    }
};

// graph class (for network-flow)
template<class FLOWTYPE> struct FlowGraph {
    // core members
    vector<vector<FlowEdge<FLOWTYPE>>> list;
    vector<pair<int,int>> pos;  // pos[i] := {vertex, order of list[vertex]} of i-th edge
    
    // constructor
    FlowGraph(int n = 0) : list(n) { }
    void init(int n = 0) {
        list.assign(n, FlowEdge<FLOWTYPE>());
        pos.clear();
    }
    
    // getter
    vector<FlowEdge<FLOWTYPE>> &operator [] (int i) {
        return list[i];
    }
    const vector<FlowEdge<FLOWTYPE>> &operator [] (int i) const {
        return list[i];
    }
    size_t size() const {
        return list.size();
    }
    FlowEdge<FLOWTYPE> &get_rev_edge(const FlowEdge<FLOWTYPE> &e) {
        if (e.from != e.to) return list[e.to][e.rev];
        else return list[e.to][e.rev + 1];
    }
    FlowEdge<FLOWTYPE> &get_edge(int i) {
        return list[pos[i].first][pos[i].second];
    }
    const FlowEdge<FLOWTYPE> &get_edge(int i) const {
        return list[pos[i].first][pos[i].second];
    }
    vector<FlowEdge<FLOWTYPE>> get_edges() const {
        vector<FlowEdge<FLOWTYPE>> edges;
        for (int i = 0; i < (int)pos.size(); ++i) {
            edges.push_back(get_edge(i));
        }
        return edges;
    }
    
    // change edges
    void reset() {
        for (int i = 0; i < (int)list.size(); ++i) {
            for (FlowEdge<FLOWTYPE> &e : list[i]) e.reset();
        }
    }
    void change_edge(FlowEdge<FLOWTYPE> &e, FLOWTYPE new_cap, FLOWTYPE new_flow) {
        FlowEdge<FLOWTYPE> &re = get_rev_edge(e);
        e.cap = new_cap - new_flow, e.icap = new_cap, e.flow = new_flow;
        re.cap = new_flow;
    }
    
    // add_edge
    void add_edge(int from, int to, FLOWTYPE cap) {
        pos.emplace_back(from, (int)list[from].size());
        list[from].push_back(FlowEdge<FLOWTYPE>((int)list[to].size(), from, to, cap));
        list[to].push_back(FlowEdge<FLOWTYPE>((int)list[from].size() - 1, to, from, 0));
    }

    // debug
    friend ostream& operator << (ostream& s, const FlowGraph &G) {
        const auto &edges = G.get_edges();
        for (const auto &e : edges) s << e << endl;
        return s;
    }
};

// Dinic
template<class FLOWTYPE> FLOWTYPE Dinic
 (FlowGraph<FLOWTYPE> &G, int s, int t, FLOWTYPE limit_flow)
{
    FLOWTYPE current_flow = 0;
    vector<int> level((int)G.size(), -1), iter((int)G.size(), 0);
    
    // Dinic BFS
    auto bfs = [&]() -> void {
        level.assign((int)G.size(), -1);
        level[s] = 0;
        queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (const FlowEdge<FLOWTYPE> &e : G[v]) {
                if (level[e.to] < 0 && e.cap > 0) {
                    level[e.to] = level[v] + 1;
                    if (e.to == t) return;
                    que.push(e.to);
                }
            }
        }
    };
    
    // Dinic DFS
    auto dfs = [&](auto self, int v, FLOWTYPE up_flow) {
        if (v == t) return up_flow;
        FLOWTYPE res_flow = 0;
        for (int &i = iter[v]; i < (int)G[v].size(); ++i) {
            FlowEdge<FLOWTYPE> &e = G[v][i], &re = G.get_rev_edge(e);
            if (level[v] >= level[e.to] || e.cap == 0) continue;
            FLOWTYPE flow = self(self, e.to, min(up_flow - res_flow, e.cap));
            if (flow <= 0) continue;
            res_flow += flow;
            e.cap -= flow, e.flow += flow;
            re.cap += flow, re.flow -= flow;
            if (res_flow == up_flow) break;
        }
        return res_flow;
    };
    
    // flow
    while (current_flow < limit_flow) {
        bfs();
        if (level[t] < 0) break;
        iter.assign((int)iter.size(), 0);
        while (current_flow < limit_flow) {
            FLOWTYPE flow = dfs(dfs, s, limit_flow - current_flow);
            if (!flow) break;
            current_flow += flow;
        }
    }
    return current_flow;
};

template<class FLOWTYPE> FLOWTYPE Dinic(FlowGraph<FLOWTYPE> &G, int s, int t) {
    return Dinic(G, s, t, numeric_limits<FLOWTYPE>::max());
}


int main() {
    int N, M;
    cin >> N >> M;
    vector<string> S(N);
    for (int i = 0; i < N; ++i) cin >> S[i];
    
    vector pls(N, vector(10, vector<int>()));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            int v = S[i][j]-'0';
            if (pls[i][v].size() >= N) continue;
            pls[i][v].push_back(j);
        }
    }
    
    int INF = M * N + 100;
    int low = 0, high = INF;
    while (high - low > 1) {
        int x = (low + high) / 2;
        int q = x / M, r = x % M;
        
        bool ok = false;
        for (int v = 0; v < 10; ++v) {
            int s = N + M, t = N + M + 1;
            FlowGraph<int> G(N + M + 2);
            for (int i = 0; i < N; ++i) G.add_edge(s, i, 1);
            for (int j = 0; j < M; ++j) G.add_edge(j + N, t, q + (j < r));
            for (int i = 0; i < N; ++i) {
                for (auto j : pls[i][v]) G.add_edge(i, j + N, 1);
            }
            int max_flow = Dinic(G, s, t);
            if (max_flow >= N) {
                ok = true;
                break;
            }
        }
        if (ok) high = x;
        else low = x;
    }
    
    cout << (high < INF ? low : -1) << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 320 G - Slot Strategy 2 (Hard) (橙色, 600 点)

問題概要

制約

解法メモ

コード