Codeforces ECR #169 : F. Make a Palindrome

これまたコードが短い。
https://codeforces.com/contest/2004/problem/F

問題

整数列Xに対し、f(X)とはXを回文にするために必要な以下の処理の最低実行回数とする。

• 隣接する2要素X[i]とX[i+1]を、その和の1要素に置き換える。
• 2以上の大きさの要素X[i]を選び、和がX[i]となる任意の2つの正整数の要素に分割する。

整数列Aが与えられる。
Aの連続部分列B全通りに対し、f(B)を答えよ。

解法

f(X)は基本的にはXが1要素になるまで連結するのに|X|-1かかる。
しかしXのprefixとsuffixで和が一致する場所があれば、そのようなprefixとsuffixは回文として消せるため、f(X)を2減らせる。

Aの代わりに、Aのprefix sumを取ったA'を考える。
A'[L]+A'[R] = A'[L']+A'[R']となるL＜L'＜R'＜Rがあれば、f(A[L...R])に対しそのようなprefix/suffixが1つあることになるので、部分列の長さの短い順に、A'[L]+A'[R]を数え上げて行こう。

int T;
int N;
int A[2020];
map<int,int> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		set<int> P={0};
		FOR(i,N) {
			cin>>x;
			A[i+1]=A[i]+x;
			P.insert(A[i+1]);
		}
		ll ret=0;
		M.clear();
		for(int l=0;l<=N;l++) {
			for(i=0;i+l<=N;i++) {
				x=A[i]+A[i+l];
				ret+=l;
				ret-=2*(M[x]++);
				if(x%2||P.count(x/2)==0) ret--;
			}
		}
		
		cout<<ret<<endl;
	}
}

まとめ

これ本番O(N^3)になっちゃって減らす方法思いつかなかったな…。