Codeforces #285 Div1 C. Misha and Palindrome Degree

最初尺取法で行ったのが失敗だったな。
http://codeforces.com/contest/504/problem/C

問題

N要素の数列A[i]が与えられる。
このうち、ある部分列A[L..R]を任意に並べ替えてA全体を回文にできるような(L,R)(L≦R)の組み合わせ数を求めよ。

解法

全体がすでに回文の時は任意のL,Rが解になるので答えはN*(N+1)/2。

そうでない場合、C要素のprefixとC要素のsuffixの反転が一致して、先頭および末尾(C+1)要素目が一致しなくなるA[C]!=A[N-1-C]となるようなCが存在する。

A全体が回文となるためには、並べ替える範囲(L,R)は最低Cか(N-1-C)のどちらかは含めなければならない。

• A[C]～A[N-1-C]全体を並べ替えて回文が作成可能なら、L≦C、(N-1-C)≦Rとなる(L,R)はすべて条件を満たすのでそのようなL,Rの取り方は(C+1)*(C+1)通り。
• 次にA[C]を含んでA[N-1-C]を含まないようなL,Rの取り方を考える。
  • A[C]～A[x]を並べ替えれば全体を回文に出来る最小のxを求められれば、L≦C、x≦R＜N-1-Cとなる(L,R)は条件を満たすので、そのような(L,R)は(C+1)*(N-2*C-x-2)通り。
• 同様にA[C]を含まずA[N-1-C]を含むようなL,Rの取り方を考える。
  • A[y]～A[R]を並べ替えれば全体を回文に出来る最大のyを求められれば、L≦y、N-1-C≦Rとなる(L,R)は条件を満たすので、そのような(L,R)は(C+1)*(N-2*C-y-2)通り。

問題は「全体を回文に出来る最小のx,y」の求め方だが、これは二分探索を用いてO(N*logN)で求めることができる。

ll N,C;
int A[101000];
ll ret;

int ok(int V) {
	int i,j,k;
	map<int,int> M;
	
	if(V<N/2) {
		FOR(i,N) {
			if(i<=V) M[A[i]]++;
			else if(N-1-i<=V) {
				if(M[A[i]]--==0) return false;
			}
			else if(A[i]!=A[N-i-1]) return false;
		}
		return true;
	}
	else {
		FOR(i,N) {
			if(i<=V) M[A[i]]++;
			else if(M[A[i]]--==0) return false;
		}
		j=0;
		ITR(it,M) j+=it->second%2;
		return j==N%2;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	FOR(C,N) if(A[C]!=A[N-1-C]) break;
	if(C==N) {
		cout<<N*(N+1)/2<<endl;
		return;
	}
	N-=2*C;
	FOR(i,N) A[i]=A[i+C];
	if(!ok(N-1)) return _P("0\n");
	
	ret += (C+1)*(C+1);
	FOR(i,2) {
		x=0;
		for(j=20;j>=0;j--) if(x+(1<<j)<=N-2 && !ok(x+(1<<j))) x+=1<<j;
		ret += (C+1)*(N-x-2);
		reverse(A,A+N);
	}
	cout<<ret<<endl;
}

まとめ

本番、真ん中から順にL,Rの範囲を広げていくアプローチは思いついたが、これは逆に外側から狭めていくアプローチだな。