kmjp's blog

競技プログラミング参加記です

LeetCode Biweekly Contest 18 : 1330. Reverse Subarray To Maximize Array Value

難易度8すら珍しいのにいきなり10でびっくり。
https://leetcode.com/contest/biweekly-contest-18/problems/reverse-subarray-to-maximize-array-value/

問題

整数列のスコアを、隣接要素の差の絶対値の総和とする。
N要素の整数列Aが与えられる。区間を1つ選択し、その中身を反転させることができるとき、スコアの最大値を求めよ。

解法

1要素だけ選択すれば実質何もしない、という手が取れる。
また、区間が先頭または末尾を含むケースは自明に総当たりしよう。
それ以外の場合、区間を総当たりするとO(N^2)かかるので何とかしなければならない。

初期状態のスコアをSとし、区間[L,R]を反転したとする。
この時のスコアはS-(|A[L]-A[L-1]|+|A[R]-A[R+1]|)+(|A[L]-A[R+1]|+|A[R]-A[L-1]|)となる。この最大値を求めよう。

A[L]-A[L-1] A[R]-A[R+1] の部分はLとR独立に計算できるが、問題は A[L]-A[R+1] + A[R]-A[L-1] の部分である。

ただこれは言い換えると、max(A[L]-A[R+1], A[R+1]-A[L])+max(A[R]-A[L-1], A[L-1]-A[R]) と置くことができる。
よって、それぞれどちらがmaxとなるかを2*2で4通り試してしまえばよい。

すなわち以下の4式の最大値を取ればよい。以下のようにするとLに関する項とRに関する項が分離でき、O(N)で処理できる。

  • S-(|A[L]-A[L-1]|+|A[R]-A[R+1]|)+A[L]-A[R+1]+A[R]-A[L-1]
  • S-(|A[L]-A[L-1]|+|A[R]-A[R+1]|)-A[L]+A[R+1]+A[R]-A[L-1]
  • S-(|A[L]-A[L-1]|+|A[R]-A[R+1]|)+A[L]-A[R+1]-A[R]+A[L-1]
  • S-(|A[L]-A[L-1]|+|A[R]-A[R+1]|)-A[L]+A[R+1]-A[R]+A[L-1]
class Solution {
public:
    int maxValueAfterReverse(vector<int>& V) {
		int N=V.size();
		ll S=0;
		int i;
		FOR(i,N-1) S+=abs(V[i]-V[i+1]);
		ll add=0;
		ll hoge[4];
		FOR(i,4) hoge[i]=-(1LL<<60);
		FOR(i,N-1) {
			
			add=max(add,hoge[0]-(V[i+1]+V[i])-abs(V[i+1]-V[i]));
			add=max(add,hoge[1]-(V[i+1]-V[i])-abs(V[i+1]-V[i]));
			add=max(add,hoge[2]-(-V[i+1]+V[i])-abs(V[i+1]-V[i]));
			add=max(add,hoge[3]-(-V[i+1]-V[i])-abs(V[i+1]-V[i]));
			
			hoge[0]=max(hoge[0],V[i+1]+V[i]-1LL*abs(V[i+1]-V[i]));
			hoge[1]=max(hoge[1],V[i+1]-V[i]-1LL*abs(V[i+1]-V[i]));
			hoge[2]=max(hoge[2],-V[i+1]+V[i]-1LL*abs(V[i+1]-V[i]));
			hoge[3]=max(hoge[3],-V[i+1]-V[i]-1LL*abs(V[i+1]-V[i]));
		}
		
		// 端
		FOR(i,N-1) add=max(add,1LL*abs(V[N-1]-V[i])-abs(V[i+1]-V[i]));
		FOR(i,N-1) add=max(add,1LL*abs(V[i+1]-V[0])-abs(V[i+1]-V[i]));
		
		cout<<S<<" "<<add<<endl;
		return S+add;
		
        
    }
};

まとめ

難易度10とはいえSRMでいうDiv1 500ptぐらい?