Codeforces #768 : Div1 D. Flipping Range

Div1 Dの割には簡単。
https://codeforces.com/contest/1630/problem/D

問題

整数列Aと、正整数集合Bが与えられる。
以下の処理を任意回数行えるとする。

• x∈Bを選び、Aから連続するx要素を選んで正負反転する

Aの総和の最大値を求めよ。

解法

結局g=GCD(B)単位で正負反転できることになる。
Aをg個ごとの要素に分けたとする。
総反転回数の偶奇を定めると、各0≦j＜gそれぞれにおいて、A[k*g+j]となる要素における反転回数の偶奇を定めるとその範囲で自由に正負反転できる。
これを踏まえ、総反転回数の偶奇それぞれのケースでAの総和の最大化を図ろう。

int T;
int N,M;
int A[1010101],B[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&N);
		scanf("%d",&M);
		FOR(i,N) scanf("%d",&A[i]);
		int G=0;
		FOR(i,M) {
			scanf("%d",&B[i]);
			G=__gcd(G,B[i]);
		}
		
		ll ret=0;
		if(G==1) {
			FOR(i,N) ret+=abs(A[i]);
		}
		else {
			ret=-1LL<<60;
			FOR(y,2) {
				ll sum=0;
				FOR(i,G) {
					vector<ll> p,m;
					for(x=i;x<N;x+=G) {
						if(A[x]>=0) p.push_back(A[x]);
						else m.push_back(-A[x]);
					}
					sort(ALL(p));
					sort(ALL(m));
					
					if(y==0) {
						if(m.size()%2) {
							if(p.size()&&p[0]<m[0]) {
								p[0]=-p[0];
							}
							else {
								m[0]=-m[0];
							}
						}
					}
					else {
						if(m.size()%2==0) {
							if(p.size()&&m.size()) {
								if(p[0]<m[0]) p[0]=-p[0];
								else m[0]=-m[0];
							}
							else if(p.size()) p[0]=-p[0];
							else m[0]=-m[0];
						}
					}
					FORR(a,p) sum+=a;
					FORR(a,m) sum+=a;
				}
				ret=max(ret,sum);
			}
		}
		cout<<ret<<endl;
	}
}

まとめ

本番割とすんなり思いつけたな。