難易度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ぐらい?