AOJ 2443

探索。答えはn-1以下であることとか、半分全列挙系を使えばいいとかを考えればいける。手元でテストするのが重過ぎる。

#include<stdio.h>
#include<algorithm>
using namespace std;
int b[10];
long long c[5][4200000];
long long d[5][4200000];
int C[5];
int D[5];
long long p10[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000LL};
int main(){
	int a;scanf("%d",&a);
	long long S=0;
	for(int i=0;i<a;i++){
		scanf("%d",b+i);
		b[i]--;
		S*=10;
		S+=b[i];
	}
	int ans=a-1;
	int start=123456789;
	for(int i=0;i<10-a;i++)start/=10;
	c[0][C[0]++]=start;
	d[0][D[0]++]=S;
	for(int i=0;i<4;i++){
	//	printf("%d %d\n",C[i],D[i]);
		for(int j=0;j<C[i];j++){
			for(int k=0;k<a;k++){
				for(int l=k+1;l<a;l++){
					long long TO=0;
					for(int m=0;m<a;m++){
						TO*=10;
						if(k<=m&&m<=l)TO+=c[i][j]%p10[a-k-l+m]/p10[a-k-l+m-1];
						else TO+=c[i][j]%p10[a-m]/p10[a-1-m];
					}
					c[i+1][C[i+1]++]=TO;
				}
			}
		}
		for(int j=0;j<D[i];j++){
			for(int k=0;k<a;k++){
				for(int l=k+1;l<a;l++){
					long long TO=0;
					for(int m=0;m<a;m++){
						TO*=10;
						if(k<=m&&m<=l)TO+=d[i][j]%p10[a-k-l+m]/p10[a-k-l+m-1];
						else TO+=d[i][j]%p10[a-m]/p10[a-1-m];
					}
					d[i+1][D[i+1]++]=TO;
				}
			}
		}
	}
	for(int i=0;i<5;i++){
		std::sort(d[i],d[i]+D[i]);
	}
	for(int i=0;i<a-1;i++){
		int n=i/2;
		bool ok=false;
		for(int j=0;j<C[n];j++)if(binary_search(d[i-n],d[i-n]+D[i-n],c[n][j]))ok=true;
		if(ok){
			printf("%d\n",i);
			return 0;
		}
	}
	printf("%d\n",ans);
}