ARC080 F - Prime Flip

最初見た時こんなの無理だろと思ったが、期間をおいて考え直したら分かった。
F - Prime Flip

問題

無限枚のカードがある。カードには1番から番号が振られている。最初x[1], ..., x[N]番目のカードは表向きで、それ以外は裏向きである。
以下の操作を何回か行うことができる。

  • 3以上の素数pを選ぶ。連続するp枚のカードをひっくり返す。

最終的に全てのカードを裏向きにする時、操作回数の最小値を求めよ。

  • 1 <= N <= 100
  • xはソートされている

解法

まず、範囲クエリなのでimos法を使い、Z/2Zの元を要素として持つ配列aに以下の操作を繰り返して全て0にする問題に変換する:

  • 3以上の素数pと正の整数uを選ぶ。a[u] += 1, a[u + p] += 1を同時に行う。

ここで、a[u]とa[v]を同時に1から0にするのに必要なコストを考えよう。v - uが3以上の素数なら1である。v - uが偶数の時、素数がたくさんあることを考えるとp1 - p2 = v - uなる素数p1, p2があるので、コストは2である。v - uが素数でない奇数の時、同様にコストは3である。
よってa[u] = 1であるような奇数と偶数をマッチングし、マッチングできたものをコスト1でマッチング、できなかったものをコスト2または3でマッチングするという実行可能解が存在することが分かる。以降最適解の中には必ずこの形のものがあることを証明する。
最適解でflipする整数全体を頂点集合とし、同時にflipする整数の間に辺を設けた無向グラフGを考える。このグラフは単純であるとしてよい。次数3以上の頂点は、上の議論を用いて次数のうち2個を別の整数にすることができるので、Gの頂点は全て次数2以下としてよい。
次数2以下の頂点からなるグラフはパスかサイクルかその直和である。サイクルは無駄なのでないとしてよい。Gの各パスについて、上の議論およびGの最適性からそれらは長さ3以下である。

登場する典型

  • Z/2Z上の範囲加算クエリをたくさん飛ばせるので、imosして2点更新クエリにする
  • 素数はたくさんあるので、2, 3個組み合わせれば全ての整数を表現できる
  • 最適解が特定の形を持つことを示し、探索すべき範囲を減らす

実装上の注意点

  • bipartite_matchingの内部で、n = 0の時にg[0]を参照しないようにする(2敗(は?))
  • Dinic法で殴る際は、辺の重みを適切に設定する(この場合全て1) (1敗)

提出: Submission #3957344 - AtCoder Regular Contest 080 (Rust)

fn prime_sieve(n: usize) -> Vec<bool> {
    let mut ans = vec![true; n];
    ans[0] = false;
    ans[1] = false;
    for i in 2 .. n {
        if !ans[i] { continue; }
        for j in 2 .. (n - 1) / i + 1 {
            ans[i * j] = false;
        }
    }
    ans
}

fn bipartite_matching(g: &[Vec<bool>]) -> usize {
    let n = g.len();
    if n == 0 { return 0; }
    let m = g[0].len();
    let mut to = vec![None; m];
    let mut visited = vec![false; n];
    let mut ans = 0;
    fn augment(v: usize, g: &[Vec<bool>],
               visited: &mut [bool], to: &mut [Option<usize>])
               -> bool {
        if visited[v] { return false; }
        visited[v] = true;
        for i in 0 .. g[v].len() {
            if !g[v][i] { continue; }
            if let Some(w) = to[i] {
                if augment(w, g, visited, to) {
                    to[i] = Some(v); return true;
                }
            } else {
                to[i] = Some(v); return true;
            }
        }
        false
    }
    for i in 0 .. n {
        for v in visited.iter_mut() { *v = false; }
        if augment(i, &g, &mut visited, &mut to) { ans += 1; }
    }
    ans
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! { x: [i64] }
    const W: usize = 1 << 24;
    let is_prime = prime_sieve(W);
    let mut hs = HashSet::new();
    for x in x {
        if hs.contains(&x) {
            hs.remove(&x);
        } else {
            hs.insert(x);
        }
        let x = x + 1;
        if hs.contains(&x) {
            hs.remove(&x);
        } else {
            hs.insert(x);
        }
    }
    let mut even = Vec::new();
    let mut odd = Vec::new();
    for x in hs {
        if x % 2 == 0 { even.push(x); }
        else { odd.push(x); }
    }
    let n = even.len();
    let m = odd.len();
    let mut g = vec![vec![false; m]; n];
    for i in 0 .. n {
        for j in 0 .. m {
            if is_prime[(even[i] - odd[j]).abs() as usize] {
                g[i][j] = true;
            }
        }
    }
    let size = bipartite_matching(&g);
    let mut tot = 3 * ((n - size) % 2);
    tot += 2 * ((n - size) / 2);
    tot += 2 * ((m - size) / 2);
    tot += size;
    puts!("{}\n", tot);
}

まとめ

それっぽい方針を思いついた後の正当性の証明に手こずった。