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"; } }
そもそも差をとるところから間違ってて笑った。これくらいのステップ数の問題が解けるようになると楽しそう。