2019-12-17

AtCoder ARC 085 E - MUL (橙色, 700 点)

AtCoder AtCoder700点 ARC-E フロー最小カット最小カット:PSP(燃やす埋める) 数列制約条件:2-SAT グラフ橙色diff けんちょん本演習問題操作操作:上書き【問題集】フローのステップアップ【問題集】フローの入門解空間:O(2^N)通りの選択肢そのまま覚えたいシンプル設定の中堅以上の典型問題中堅以上の典型要素を詰め合わせた教育的問題マトロイドと劣モジュラ関数

いわゆる「燃やす埋める」の典型です。

問題へのリンク

問題概要

$N$ 個の整数 $a_1, \dots, a_N$ が与えられます (負値もありえます)。今、各 $i = 1, 2, \dots, N$ に対して、以下の操作を行うか行わないかを選んで行うことができます。

$i$ 番目の操作: $i$ の倍数であるようなすべての $j$ に対して、 $a_j$ の値を 0 にする

操作を行った後の $a_1 + \dots + a_N$ の値として考えられる最大値を求めてください。

制約

$1 \le N \le 100$

考えたこと

いかにも「燃やす埋める」の雰囲気が漂う。こういう問題では、まずは変数を立てて考えると考えやすいように思う。

$x_i$ を、 $a_i = 0$ にするときは 1、 $a_i$ をそのままにするときは 0 であるような 0-1 整数変数とする。このとき、制約条件は

$j$ % $i$ == 0 であるような任意の組 $(i, j)$ に対して
「 $x_i = 1$ であるにもかかわらず $x_j = 0$ である場合」は $\infty$ のペナルティ

という風に解釈することができる。そうすると燃やす埋めるが使える形になる。

燃やす埋めるの概要

0-1 変数が 2 個 ( $x_{0}, x_{1}$ ) あるとして、

操作 $i = 0, 1$ を行うコストが $a_{i}$
操作 $i = 0, 1$ を行わないコストが $b_i$
$x_{0} = 1$ (0 には操作を行う) かつ $x_{1} = 0$ (1 には操作を行わない) である場合は $\infty$ のペナルティ

という状況を、下図のような最小カットで表現することができる。

今回の問題の場合、以下のようになる。

a_i >= 0 のとき

操作を行わない方がよいので

操作 $i$ を行うコストが $a_i$
操作 $i$ を行わないコストが $0$

a_i < 0 のとき

操作を行った方がよいので

操作 $i$ を行うコストが $0$
操作 $i$ を行わないコストが $- a_i$

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// edge class (for network-flow)
template<class FLOWTYPE> struct Edge {
    int rev, from, to;
    FLOWTYPE cap, icap;
    Edge(int r, int f, int t, FLOWTYPE c) : rev(r), from(f), to(t), cap(c), icap(c) {}
    friend ostream& operator << (ostream& s, const Edge& E) {
        if (E.cap > 0) return s << E.from << "->" << E.to << '(' << E.cap << ')';
        else return s;
    }
};

// graph class (for network-flow)
template<class FLOWTYPE> struct Graph {
    vector<vector<Edge<FLOWTYPE> > > list;
    
    Graph(int n = 0) : list(n) { }
    void init(int n = 0) { list.clear(); list.resize(n); }
    void reset() { for (int i = 0; i < (int)list.size(); ++i) for (int j = 0; j < list[i].size(); ++j) list[i][j].cap = list[i][j].icap; }
    inline vector<Edge<FLOWTYPE> >& operator [] (int i) { return list[i]; }
    inline const size_t size() const { return list.size(); }
    
    inline Edge<FLOWTYPE> &redge(Edge<FLOWTYPE> e) {
        if (e.from != e.to) return list[e.to][e.rev];
        else return list[e.to][e.rev + 1];
    }
    
    void addedge(int from, int to, FLOWTYPE cap) {
        list[from].push_back(Edge<FLOWTYPE>((int)list[to].size(), from, to, cap));
        list[to].push_back(Edge<FLOWTYPE>((int)list[from].size() - 1, to, from, 0));
    }
    
    void add_undirected_edge(int from, int to, FLOWTYPE cap) {
        list[from].push_back(Edge<FLOWTYPE>((int)list[to].size(), from, to, cap));
        list[to].push_back(Edge<FLOWTYPE>((int)list[from].size() - 1, to, from, cap));
    }
};

// Dinic's algorithm
template<class FLOWTYPE> struct Dinic {
    const FLOWTYPE INF = 1LL<<59; // to be set
    vector<int> level, iter;

    Dinic() { }
    void dibfs(Graph<FLOWTYPE> &G, int s) {
        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 (int i = 0; i < G[v].size(); ++i) {
                Edge<FLOWTYPE> &e = G[v][i];
                if (level[e.to] < 0 && e.cap > 0) {
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    
    FLOWTYPE didfs(Graph<FLOWTYPE> &G, int v, int t, FLOWTYPE f) {
        if (v == t) return f;
        for (int &i = iter[v]; i < G[v].size(); ++i) {
            Edge<FLOWTYPE> &e = G[v][i], &re = G.redge(e);
            if (level[v] < level[e.to] && e.cap > 0) {
                FLOWTYPE d = didfs(G, e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    re.cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    
    FLOWTYPE solve(Graph<FLOWTYPE> &G, int s, int t) {
        level.assign((int)G.size(), -1); iter.assign((int)G.size(), 0);
        FLOWTYPE res = 0;
        while (true) {
            dibfs(G, s);
            if (level[t] < 0) return res;
            for (int i = 0; i < (int)iter.size(); ++i) iter[i] = 0;
            FLOWTYPE flow = 0;
            while ((flow = didfs(G, s, t, INF)) > 0) {
                res += flow;
            }
        }
    }
};

const long long INF = 1LL<<55;
int main() {
    int N; cin >> N;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    Dinic<long long> di;
    Graph<long long> G(N+2);
    int s = N, t = N+1;     

    long long offset = 0;
    for (int i = 0; i < N; ++i) {
        if (a[i] >= 0) {
            G.addedge(s, i, 0);
            G.addedge(i, t, a[i]);
            offset += a[i];
        }
        else {
            G.addedge(s, i, -a[i]);
            G.addedge(i, t, 0);
        }
    }
    
    for (int i = 0; i < N; ++i) {
        for (int j = i+1; j < N; ++j) {
            if ((j+1) % (i+1) == 0) {
                G.addedge(i, j, INF);
            }
        }
    }
    long long res = di.solve(G, s, t);
    cout << offset - res << endl;
}

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

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