AtCoder Regular Contest 080F: Prime Flip

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

まず列の差をとって区間の問題を距離が奇素数の2点を反転させてすべて0にする問題に帰着させる。

座標i,jにある1を対応させるときのコストは
|i-j|が奇素数→1
|i-j|が偶数→2
|i-j|が奇素数ではない奇数→3
となる。これは今N<=10^7であり、ゴールドバッハ予想が成立することから示せる。

あとは座標が奇数の頂点と偶数の頂点に分け、なるべくコスト1の辺を使ってマッチングを作ればいい。これは最大フローで解ける。

int N, M;
int E, O;
int A[110], B[210];
int C[210], D[210];

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

void solve() {
	cin >> N;
	M = 0;
	rep(i, 0, N) cin >> A[i];
	rep(i, 0, N) {
		int t1 = (find(A, A + N, A[i] - 1) != A + N);
		int t2 = (find(A, A + N, A[i] + 1) != A + N);
		if(t1 == 0) B[M++] = A[i] - 1;
		if(t2 == 0) B[M++] = A[i];
	}
	M = unique(B, B + M) - B;
	int s = M, t = M + 1;
	MF::init(M + 2);

	rep(i, 0, M) {
		if(B[i] % 2 == 0) C[E++] = B[i];
		else D[O++] = B[i];
	}
	rep(i, 0, E) {
		rep(j, 0, O) {
			if(prime(abs(C[i] - D[j]))) {
				MF::add_edge(i, j + E, 1);
			}
		}
	}
	rep(i, 0, E) MF::add_edge(s, i, 1);
	rep(i, 0, O) MF::add_edge(i + E, t, 1);

	int res = MF::get(s, t);
	if((E - res) % 2 == 0) {
		cout << res + (E - res) + (O - res) << "\n";
	}
	else {
		cout << res + (E - res - 1) + (O - res - 1) + 3 << "\n";
	}
}

そもそも差をとるところから間違ってて笑った。これくらいのステップ数の問題が解けるようになると楽しそう。