http://arc080.contest.atcoder.jp/tasks/arc080_d

問題概要

1, 2, ...と順に番号の振られた無限枚のカードと、N要素の数列Xがある。数列Xに含まれる番号のカードは表向きで、それ以外は裏向きである。奇素数pと連続するp枚のカードを自由に選びそれらを裏返す、という操作を繰り返すとき、すべてのカードを裏向きにするために必要な最小の操作回数を求めよ。

N <= 100, max(X) <= 10⁷

解法

表向きのカードを1, 裏向きのカードを0とすると、カードを0/1の列で表すことができる。この数列をAとし、また数列Aについてxorで階差をとった数列をBとする。こうすると「Aにおいて区間[x, x+p]をflipする」という操作が「Bにおいてx, x+pの2点をflipする」とみなせるようになる。なぜなら隣り合う点を同時にflipしてもxorの値は変わらず、端点だけで変化が生じるためである。これで連続する列に対する操作を2点のみに対する操作に変換することができた。

次にBにおいてビットが立っている点のペア(i, j)を選び、これらを両方0にすることを考える。これを達成するための最小操作回数は実のところ1回, 2回, 3回のいずれかに限定される。

コスト1. |i - j| が奇素数の場合（自明）
コスト2. |i - j| が偶数の場合 (cf. ゴールドバッハの予想）
コスト3. |i - j| が素数でない奇数の場合（1回の操作で偶数差にできるため）

以上より最終的な答えは、まずコスト1で消せるだけの奇素数差ペアを消し、次にコスト2で消せるだけの偶数差ペアを消し、最後に残った奇数差のペアをコスト3で消すことで得ることができる。ここで「コスト1で消せる最大のペア数」は2部グラフの最大マッチングで解くことができる。すなわちビットが立っている点を奇数と偶数でグループ分けし、その間で差が奇素数であるものに辺を張る。このようにしてできた2部グラフの最大マッチングがイコール「コスト1で消せる最大のペア数」になる。これが求まったらあとは貪欲で、残った奇数グループ、偶数グループの中でコスト2のペアをできるだけ作り、最後に余った点があればコスト3でペアを作る。以上で払ったコストの合計が解となる。

感想

①階差数列をとることで2点に対する操作に落とす ②ペアを消すためのコストが1, 2, 3の3パターンしかないことに気づく ③フローでがんばれることに気づいてがんばるという風に複数の山場がある問題ですが、①の時点でムズすぎる……。 ②③もパッと思いつけるほどではないように見えるし、奇跡的に①が思いついても自分の実力ではまず詰め切れそうにない。バイナリ列の区間に対する操作は階差を取ると良い感じになることがある、っていうのが割と汎用性の高いテクなのか、それともこのくらいのレベルになるとこういうのを都度アドホックに発見していく力が必要なのか……

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
void main() {
    auto N = readln.chomp.to!int;
    auto A = readln.split.map!(to!int).array;
    
    int[] B;
    foreach (a; A) {
        foreach (b; a-1..a+1) {
            if (B.length > 0 && B[$-1] == b) B.popBack;
            else B ~= b;
        }
    }
 
    auto P = new bool[](10^^7 + 10);
    fill(P, true);
    P[0] = P[1] = false;
    for (int i = 2; i < 10^^7 + 10; i++) {
        if (!P[i]) continue;
        for (int j = i + i; j < 10^^7 + 10; j += i) P[j] = false;
    }
 
 
    B.sort!"a % 2 > b % 2"();
    int M = B.length.to!int;
    int source = M;
    int sink = M + 1;
    int odd = B.map!(b => b % 2).sum;
    int even = B.map!(b => 1 - b % 2).sum;
    auto FF = new FordFulkerson(M + 2, source, sink);
    foreach (i; 0..odd) FF.add_edge(source, i, 1);
    foreach (i; odd..odd+even) FF.add_edge(i, sink, 1);
    foreach (i; 0..odd) {
        foreach (j; odd..odd+even) {
            if (P[abs(B[i] - B[j])]) FF.add_edge(i, j, 1);
        }
    }
    
    int one = FF.run;
    odd -= one;
    even -= one;
    int two = odd / 2 + even / 2;
    int three = odd % 2;
 
    writeln(one + two * 2 + three * 3);
}
 
 
 
class FordFulkerson {
    int N, source, sink;
    int[][] adj;
    int[][] flow;
    bool[] used;
 
    this(int n, int s, int t) {
        N = n;
        source = s;
        sink = t;
        assert (s >= 0 && s < N && t >= 0 && t < N);
        adj = new int[][](N);
        flow = new int[][](N, N);
        used = new bool[](N);
    }
 
    void add_edge(int from, int to, int cap) {
        adj[from] ~= to;
        adj[to] ~= from;
        flow[from][to] = cap;
    }
 
    int dfs(int v, int min_cap) {
        if (v == sink)
            return min_cap;
        if (used[v])
            return 0;
        used[v] = true;
        foreach (to; adj[v]) {
            if (!used[to] && flow[v][to] > 0) {
                auto bottleneck = dfs(to, min(min_cap, flow[v][to]));
                if (bottleneck == 0) continue;
                flow[v][to] -= bottleneck;
                flow[to][v] += bottleneck;
                return bottleneck;
            }
        }
        return 0;
    }
 
    int run() {
        int ret = 0;
        while (true) {
            foreach (i; 0..N) used[i] = false;
            int f = dfs(source, int.max);
            if (f > 0)
                ret += f;
            else
                return ret;
        }
    }
}

nebukuro09の日記

AtCoder Regular Contest 080 F - Prime Flip

問題概要

解法

感想

コード (D言語)