AtCoder ARC #080 : F - Prime Flip

一歩考察が及ばず。
http://arc080.contest.atcoder.jp/tasks/arc080_d

問題

1,2,3...と順に番号の振られた無限枚のカードがある。
このうちN枚のカードが表向きであり、その番号X[i]が与えられる。

これらのカード群に対し、奇素数pを指定し、連続するp枚を裏返す、という処理を繰り返す。
全カードを裏向きにするには、最小何回処理を行う必要があるか。

解法

数列A[i]を、初期状態でi番のカードが表向きか否かを示す0/1の真偽値とする。
さらに、数列B[i]をA[i]の階差数列、すなわちB[i]=A[i]^A[i-1]とする。
B[i]がすべてゼロになれば、A[i]もゼロなので、B[i]をゼロにすることを考えよう。
なお、B[i]のうち1となる要素は必ず偶数個である。

カードをp枚裏返す処理は、数列BにおいてB[i]とB[i+p]を反転させる行為である。
よって、B[i]もB[i+p]も1であるようなi,pが存在するなら、それらを同時に反転させるのが少ない処理回数でカードを裏向きにできてよい。
これをもう少し整理する。
B[x]=B[y]=1である２値x＜yをそれぞれ0にするには何回処理が必要かを考える。

• y-xが奇素数 : 上記のとおり1回
• y-xが偶数 : ゴールドバッハ予想より2回
• y-xが奇数かつ合成数 : 3回

初期状態でBは偶数個1なので、上記の合計処理回数が最小となるようマッチングを考える。
まずB[x]=1となるxを、偶数と奇数で分類しよう。
次に、偶数に対応する点と奇数に対応する点で二部マッチングを考える。両者の間は、差が奇素数であれば辺を張る。
このグラフでの最大マッチングは、1回でともに反転できるB[x],B[y]の対に相当する。

残った頂点群は、まず偶数同士、奇数同士でマッチングして２手で反転し、それでも余った場合は３手で反転させればよい。

int N;
int X[101];
vector<int> E,O;

template<class V> class MaxFlow_Ford {
public:
	struct edge { int to,reve;V cap;};
	static const int MV = 10000;
	vector<edge> E[MV];
	int vis[MV];
	void add_edge(int x,int y,V cap,bool undir=false) {
		E[x].push_back((edge){y,(int)E[y].size(),cap});
		E[y].push_back((edge){x,(int)E[x].size()-1,undir?cap:0});
	}
	V dfs(int from,int to,V cf) {
		V tf;
		if(from==to) return cf;
		vis[from]=1;
		FORR(e,E[from]) if(vis[e.to]==0 && e.cap>0 && (tf = dfs(e.to,to,min(cf,e.cap)))>0) {
			e.cap -= tf;
			E[e.to][e.reve].cap += tf;
			return tf;
		}
		return 0;
	}
	V maxflow(int from, int to) {
		V fl=0,tf;
		while(1) {
			ZERO(vis);
			if((tf = dfs(from,to,numeric_limits<V>::max()))==0) return fl;
			fl+=tf;
		}
	}
};
MaxFlow_Ford<int> mf;

int prime(int x) {
	if(x<=2) return 0;
	for(int a=2;a*a<=x;a++) if(x%a==0) return 0;
	return 1;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	map<int,int> M;
	FOR(i,N) {
		cin>>X[i];
		M[X[i]]^=1;
		M[X[i]+1]^=1;
	}
	
	FORR(r,M) if(r.second) {
		if(r.first%2==0) E.push_back(r.first);
		else O.push_back(r.first);
	}
	
	FOR(x,E.size()) mf.add_edge(0,1000+x,1);
	FOR(x,O.size()) mf.add_edge(2000+x,1,1);
	FOR(x,E.size()) FOR(y,O.size()) if(prime(abs(E[x]-O[y]))) mf.add_edge(1000+x,2000+y,1);
	
	int ma=mf.maxflow(0,1);
	x=E.size()-ma;
	y=O.size()-ma;
	cout<<ma+(x/2)*2+(y/2)*2+x%2*3<<endl;
	
}

まとめ

ゴールドバッハ予想から偶数枚の反転は２手でできることまでは考察できたが、そこまでだった。