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); }
まとめ
それっぽい方針を思いついた後の正当性の証明に手こずった。