Atcoder Regular Contest 080 F. Prime Flip

Atcoder Regular Contest 080 F. Prime Flip

F: Prime Flip - AtCoder Regular Contest 080 | AtCoder

感想

解説を見た。簡単な方法に落とし込むまでの流れが好きな問題。

解法

まず区間をひっくり返すときのテクを使う。列においてある位置とその一つ前の位置を見て、それらの$\ xor\ $をとって、これを配列$\ x\ $などにいれる。imosの反転バージョンのような感じである。すると、$\ [l, r)\ $を反転する操作が、$\ x_l\ $と$\ x_r\ $のみを反転する操作になる。そして、問題はこの配列の数をすべて0にするための最小手数を求める問題に変わる。

ここで、ある位置の1を消す（位置をずらすのではなく個数を減らすという意味で）ためには、またある別の数と同時に消す他に方法はない。つまりこれらの1同士で同時に消えるペアを作って良い。以下、そのようなペアの作り方で最適なものを考える。

ある2数の位置が$\ a, b\ $だったとする。もし、$\ |a - b|\ $が3以上の素数なのだとしたら、これらは明らかに1回の操作で消せる。逆に、素数でなければ1回で消せることがないことも言える。

次に$\ |a - b|\ $が偶数であるとする。$\ |a - b| = 2\ $のときは、双子素数を使って2回の操作でこれらを消せる。$\ |a - b| \geq 4\ $のときは、ゴールドバッハの予想(ゴールドバッハの予想 - Wikipedia)によってその差を二つの素数の和で表せるのでやはり2回の操作で消せる。1回の操作で消すことは自明にできないので、これが最小回数である。

最後に$\ |a - b|\ $が奇数であり、かつ素数ではないとする。このとき、まず3回の操作で必ず消せることを示す。まず1回の操作で、$\ |a - b|\ $の値を3大きくする。すると、$\ |a - b|\ $は偶数になるので、上記よりあと2回の操作でこれを消せる。よって3回の操作で消せることがわかる。次に2回以下の操作では消せないことを示す。2回操作をするということは、3以上の素数は奇数なので、$\ |a - b|\ $の値の変化量は必ず偶数になるはずである。よってこれが0になることはない。1回の操作では当然消せないので、これで3回が最小の回数であることが示された。

あとはペアを作っていくだけである。まず位置が奇数であるグループと偶数であるグループにわけ、できるだけ1回で消せるペアをこのグループ間でつくればよい。この1回で消せるペアの数を最大化するとよいというのは割と自明だと思ったが、一応証明がeditorialには書いてあるので省略。

これは最大二部マッチングを求める問題に帰着されるので、あとはやるだけである。

実装

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

bool is_prime(int x) {
        if (x == 1) return false;
        for (int i = 2; i * i <= x; i ++) {
                if (x % i == 0) return false;
        }
        return true;
}

struct edge {
        int to, cap, rev;
};
bool used[101010];
vector<edge> g[101010];
static const int INF = 0x3f3f3f3f;
void add_edge(int from, int to, int cap) {
        g[from].push_back((edge) { to, cap, (int)g[to].size() });
        g[to].push_back((edge) { from, 0, (int)g[from].size() - 1 });
}
int dfs(int v, int t, int f) {
        if (v == t) return f;
        used[v] = true;
        for (int i = 0; i < g[v].size(); i ++) {
                edge& e = g[v][i];
                if (!used[e.to] && e.cap > 0) {
                        int d = dfs(e.to, t, min(f, e.cap));
                        if (d > 0) {
                                e.cap -= d;
                                g[e.to][e.rev].cap += d;
                                return  d;
                        }
                }
        }
        return 0;
}
int MaxFlow(int s, int t) {
        int flow = 0;
        while (true) {
                memset(used, false, sizeof(used));
                int f = dfs(s, t, INF);
                if (f == 0) return flow;
                flow += f;
        }
}

vector<int> even, odd;

void push(int x) {
        if (x & 1) odd.push_back(x);
        else even.push_back(x);
}

int main() {
        int n;
        cin >> n;
        vector<int> x(n);
        for (int i = 0; i < n; i ++) cin >> x[i];
        for (int i = 0; i < n; i ++) {
                if (i == 0 || x[i] - 1 != x[i - 1]) push(x[i]);
                if (i == n - 1 || x[i] + 1 != x[i + 1]) push(x[i] + 1);
        }
        int o = odd.size(), e = even.size();
        int s = 0, t = o + e + 1;
        for (int i = 0; i < o; i ++) add_edge(s, i + 1, 1);
        for (int i = 0; i < e; i ++) add_edge(i + o + 1, t, 1);
        for (int i = 0; i < o; i ++) {
                for (int j = 0; j < e; j ++) {
                        int d = abs(odd[i] - even[j]);
                        if ((d & 1) && is_prime(d)) add_edge(i + 1, j + o + 1, 1);
                }
        }
        int k = MaxFlow(s, t);
        int ans = k + ((e - k) / 2 + (o - k) / 2) * 2 + ((o - k) % 2) * 3;
        cout << ans << endl;
        return 0;
}