Codeforces #907 : Div2 E. Brukhovich and Exams

EよりFの方が極端に簡単だった回。
https://codeforces.com/contest/1891/problem/E

問題

N要素の整数列Aと、整数Kが与えられる。
AのうちK要素を0にできるとき、GCDが1となる隣接要素対の数を最小いくつにできるか。

解法

Aを、隣接要素のGCDが2以上のところで区切ろう。
あとはその各部分列について考えればよい。
2以上の値が連続しているところがあれば、1つおきに0にしていくとよい。
その後、余った分だけ1を0に置き換えていこう。

int T,N,K,A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	FOR(x,T) {
		cin>>N>>K;
		vector<vector<int>> V;
		int ret=0;
		FOR(i,N) {
			cin>>A[i];
			if(i&&__gcd(A[i],A[i-1])==1) ret++;
		}
		FOR(i,N) {
			if(i==0||(i&&A[i-1]==1&&A[i]!=1)) {
				V.push_back({A[i]});
			}
			else if(A[i-1]!=1&&A[i]==1) {
				V.push_back({A[i]});
			}
			else if(__gcd(A[i],A[i-1])!=1) {
				V.push_back({A[i]});
			}
			else {
				V.back().push_back(A[i]);
			}
		}
		if(V.size()==1&&V[0][0]==1) {
			FOR(i,K) A[i]=0;
			ret=0;
			FOR(i,N-1) if(A[i]||A[i+1]) ret++;
		}
		else {
			vector<int> C;
			FOR(i,V.size()) {
				if(V[i][0]!=1) {
					while(V[i].size()>=3&&K) {
						K--;
						ret-=2;
						V[i].pop_back();
						V[i].pop_back();
					}
				}
				else {
					if(i>0&&i<V.size()-1) C.push_back(V[i].size());
				}
			}
			sort(ALL(C));
			FORR(c,C) if(c<=K) {
				ret-=c+1;
				K-=c;
			}
			ret-=K;
		}
		cout<<max(0,ret)<<endl;
		
	}
}

まとめ

細かいコーナーケースを詰めるのに手間取る問題。