CODE FESTIVAL 2014 決勝 : F - 誤情報

徐々に難しくなってきた。
http://code-festival-2014-final-open.contest.atcoder.jp/tasks/code_festival_final_f

問題

N要素の整数列A[i]があるとする。
(この数列は循環しているとみなし、A[N]=A[0]とする。)
B[i]をA[i]とA[i+1]の最大公約数とする。

ここで、B[i]の候補が与えられる。
B[i]は一部誤情報が含まれている可能性があり、B[i]をすべて満たすA[i]を作ろうとすると矛盾が生じる可能性がある。
矛盾が生じなくなるような誤情報の最小数を答えよ。

解法

B[i-1]とB[i+1]の最大公約数をG[i]とする。
B[i-1]はA[i-1]とA[i]の最大公約数、B[i+1]はA[i+1]とA[i+2]の最大公約数なので、A[i-1]及びA[i]はGの倍数であるはずであり、B[i]もG[i]の倍数であるはずである。

しかしB[i]がG[i]の倍数でない場合、矛盾が生じる。
まずB[i]を１周見て矛盾が生じる箇所を求める。

次に矛盾を解消する方法だが、B[j]が誤情報であったとするとB[j-1]・B[j]・B[j+1]の３つの矛盾が解消できる。
逆に、B[i]で矛盾が生じているなら、B[i+1]が誤情報であると判断し、B[i]・B[i+1]・B[i+2]の矛盾を解消していけば良い。

後は単純な貪欲法で誤情報の数を求めればよい。
ただし、A[i]が循環しており、B[N-2]やB[N-1]が誤情報であると判断した方がいいケースもあるので、以下では開始位置をずらして３回貪欲法を行っている。

int N;
ll B[100020];
int wrong[100020],wrong2[100020];
int dp[100020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>B[i];
	FOR(i,N) if(B[i]%__gcd(B[(i+N-1)%N],B[(i+1)%N])) wrong2[i]=1;
	
	y=1<<30;
	FOR(i,3) {
		FOR(j,N) wrong[j]=wrong2[(j+i)%N];
		x=0;
		FOR(j,N) if(wrong[j]==1) x++, wrong[j]=wrong[j+1]=wrong[j+2]=0;
		y=min(y,x);
	}
	cout<<y<<endl;
}

まとめ

なかなか面白い問題。