ARC080 F : Prime Flip(1200)
作成日：2017.08.15
最終更新日：2017.08.15
問題概要
互いに異なる正の整数が1つ書かれた無限枚のカードが番号順に並んでいて、$x_i$が書かれたカードは表向きでその他は裏向きである。
操作「連続する奇素数枚のカードを選び、すべてひっくり返す」をすべてのカードが裏向きになるまで繰り返す時、操作の最小回数を求めよ。
制約
$1 \leq N \leq 100$
$1 \leq x_1 < x_2 < ... < x_N \leq 10^7$
考え方
まず1つのカードにだけ注目する。
カードが選ばれるたびにひっくり返されるので、カードの向きは選ばれた回数が偶数の時は初めの向きと同じであり、奇数の時は初めの向きとは異なる。
つまり$i$が書かれたカードが表の時に$1$、裏の時に$0$をとる$a_i$を考えると、
操作は「ある正の整数$n$と奇素数$p$について$a_i(n \leq i < n+p)$のビットを反転させる」と言い換えることができる。
また、操作の終わりは$a_i$がすべて$0$になる時である。
しかしこれは1回の操作で変化する値が多い上に個数が一定でないため考えにくい。
次に隣り合う2つのカードに注目する。
各カードの向きについては先と同様であるので、2つのカードの向きが等しいかを考える。
カードの向きが等しいかは、一方が選ばれもう一方が選ばれなかった時に限り変化する。
これは、選ばれた連続するカードか否かの境が2つのカードの間にある時である。
つまり$i$及び$i+1$が書かれたカードの向きが異なる時に$1$、そうでない時に$0$をとる$b_i$を考えると、
操作は「ある非負整数$n$と奇素数$p$について$b_n$と$b_{n+p}$のビットを反転させる」と言い換えることができる。
但し$1$が書かれたカードが選ばれている時にもうまくいくようにするため、$b_0$を$x_1 = 1$の時に$1$、そうでない時に$0$を取るとして定義する。
またそうすることで、操作の終わりは$b_i$がすべて$0$となる時となる。
これは1回の操作で変化する値は2つで一定なので考えやすそうである。
(ちなみに$b_i = a_i \: XOR \: a_{i+1}$(但し$a_0 = 0$)となっている。)
カードをひっくり返す操作は可換であるから、$n$と$p$を選ぶ時は$b_n$と$b_{n+p}$のいずれかが$1$であるものに限って良い。
この時操作をすると、$1$である$b_i$の個数は変化しないか$2$減るかのいずれかである。
そこで、その個数が$2$減るまで直前の操作により新たに$1$になった$b_i$が次の操作でビットが反転されるように選ぶことにする。
これは$b_i$のうち$1$であるものを2つ選んで$0$にする一連の操作となる。
そのような2つを$b_i , b_j(i < j)$として、最小何回の操作で$0$にできるかを考える。
まず1回の操作でできる時を考えるが、これは明らかに$j-i$が奇素数の時である。
次に2回の操作でできる時を考える。
これは$j-i$が2つの奇素数の和または差で表せる時であるが、ゴールドバッハの予想と$2=5-3,4=7-3$より$j-i$が偶数である時といえる。
また$5$以上の奇数は(偶数)$+3$で表すことができ$1=7-3-3$であるから、素数でない奇数は3回の操作でできる。
以上より初めに$b_i = 1$であるすべての$i$(偶数個ある)を適切にペアにしていけば良い。
すなわち$i$の差が偶数であるペアはコスト$2$、奇数であるペアは素数ならばコスト$1$、合成数ならばコスト$3$であるとしてコストを最小化すれば良い。
あるペアの作り方が最適となった時$i$の差が偶数であるペア2つを組み替えてコスト$1$のペアを作ることができるならば、組み替えた後も最適なペアの作り方である。
つまりコスト$1$のペアの数を最大化した時にも最適なペアの作り方が存在する。
またこの時、残りのペアはコストが小さくなるように貪欲に作っていけば良い。
あとはコスト$1$のペアの数の最大値が分かれば良い。
このようなペアの$i$の差は奇(素)数であるから$i$が偶数のものと奇数のもののマッチングと考えられる。
つまり二部グラフの最大マッチング問題であるから、最大流問題として解ける。
グラフの辺は高々$N^2$であり最大流は高々$N$であるから、Edmonds-Karp法によって十分高速に求められる。
ソースコード
マクロ等はこちら
Edmonds_Karp<T>
void put(int a , int b , T c)
始点$a$、終点$b$、容量$c$の辺をグラフに追加
T ans(int s , int t)
$s$を始点、$t$を終点とする時のグラフの最大流を取得
const int MC = 10234567;
int N;
int x[111];
bool p[MC]; //奇素数であればtrue
vector<int> V[2]; //b_i=1であるiの集合(V[0/1]:iが偶数/奇数)
Edmonds_Karp<int> solve;
int main(){
fill(p+3,p+MC,1);
for(int i = 4 ; i < MC ; i += 2) p[i] = 0;
for(int i = 3 ; i * i <= MC ; ++i) if(p[i]) for(int j = i*i ; j < MC ; j += i) p[j] = 0;
scanf("%d%d" , &N , x);
repp(i,1,N){
scanf("%d" , x + i);
if(x[i-1]+1 != x[i]){
V[x[i-1]%2].PB(x[i-1]);
V[(x[i]-1)%2].PB(x[i]-1);
}
}
V[(x[0]-1)%2].PB(x[0]-1);
V[x[N-1]%2].PB(x[N-1]);
repp(i,0,V[0].size()){
repp(j,0,V[1].size()){
if(p[abs(V[0][i]-V[1][j])]) solve.put(i,N+j,1);
}
solve.put(N*2,i,1);
}
repp(j,0,V[1].size()) solve.put(N+j,N*2+1,1);
int m = solve.ans(N*2,N*2+1);
printf("%d\n" , m + (V[0].size()-m)/2*2 + (V[1].size()-m)/2*2 + (V[0].size()-m)%2*3);
return 0;
}解法まとめ
奇素数を列挙する。(9-11行)
$b_i = 1$である$i$を偶奇に分ける。(13-21行)
差が奇素数である$i$の間に辺を張り、各要素を始点または終点とつなぐ。(22-28行)
最大マッチング数$m$だけコスト$1$のペアを作り、残ったものでコストが最小となるように貪欲にペアを作る。(29,30行)