AtCoder ARC #204 : B - Sort Permutation

計算量は想定解通りなんだけど、定数倍高速化に手間取った…。
https://atcoder.jp/contests/arc204/tasks/arc204_b

問題

整数N,Kと、1～NKの順列Pが与えられる。
Pの2要素を選んで入れ替えることを繰り返し、Pを昇順にしたい。
その際、P[i]とP[j]を入れ替えるときに|i-j|がNの倍数だと1ポイント入る。

最小の操作回数でPを昇順にするとき、得られるポイントの最大値を求めよ。

解法

(i→P[i])に辺を張ったFunction Graphを考える。

各閉路において、indexを列挙した数列Aを考える。また、indexの値はあらかじめNで割った余りにしておく。
この数列の先頭と末尾がつなっているとき、残り1要素になるまで、1要素ずつ選んで削除するが、その際次の要素が同じ値であれば1ポイント入る。
閉路ごとに、得られるポイントの最大値を考える。

最後に残る2要素がA[L]、A[R]として総当たりすることを考える、そのためには、そこまでにA[L...R]及びA[R.|A|-1,0..L]のそれぞれの中身を削除しないといけない。
f(L,R) := A[L...R]を、最後A[R]だけ残るように削除するまでに得られるポイント数の最大値
としてメモ化再帰で解く。
削除の仕方は以下が考えられる。

• A[L]の削除の際ポイントを期待しない。その場合、f(L,R)=f(L+1,R)
• A[L]=A[x]となるxがあるとき、A[(L+1)...(x-1)]を削除しないといけないので、f(L,R)=1+f(L+1,x)+f(x,R)

なお、この問題ではA[L]=A[x]となるxは高々K個しかないで、O(N^2*K^3)で解ける。

int N,K;
int P[5050],R[5050];

template<int NV> struct FunctionGraph {
	//input
	int E[NV];
	//output
	int N;
	int NG; //閉路数
	int nex[61][NV];  // 2^i先の点
	vector<int> RE[NV]; // 逆向き辺
	vector<int> G[NV]; // 閉路
	int GS[NV]; // 閉路長
	int NC[NV]; // subtreeの要素数
	int Gid[NV],Gindex[NV]; // 閉路IDとその中のindex。閉路外の場合、閉路IDは最寄りの閉路だがindexは-1
	int GV[NV], D[NV]; //最寄りの閉路の点とそこまでの距離
	int dfs(int cur,int id,int d) {
		GV[cur]=id;
		Gid[cur]=Gid[id];
		D[cur]=d;
		NC[cur]=1;
		FORR(e,RE[cur]) if(Gindex[e]==-1) NC[cur]+=dfs(e,id,d+1);
		return NC[cur];
	}
	int move(int cur,ll step) { // step先に進む
		int i;
		FOR(i,60) if(step&(1LL<<i)) cur=nex[i][cur];
		return cur;
	}
	void build(int N_) {
		N=N_;
		int i,j;
		vector<int> in(N);
		FOR(i,N) {
			RE[i].clear();
			G[i].clear();
			Gindex[i]=-2;
			nex[0][i]=E[i];
		}
		NG=0;
		FOR(i,N) {
			RE[E[i]].push_back(i);
			in[E[i]]++;
		}
		queue<int> Q;
		FOR(i,N) if(in[i]==0) Q.push(i);
		while(Q.size()) {
			int cur=Q.front();
			Q.pop();
			Gindex[cur]=-1;
			if(--in[E[cur]]==0) Q.push(E[cur]);
		}
		FOR(i,N) if(Gindex[i]==-2) {
			G[NG].push_back(i);
			while(1) {
				int x=G[NG].back();
				Gid[x]=NG;
				Gindex[x]=G[NG].size()-1;
				x=E[x];
				if(x==G[NG][0]) break;
				G[NG].push_back(x);
			}
			GS[NG]=G[NG].size();
			NG++;
		}
		FOR(i,N) if(Gindex[i]>=0) dfs(i,i,0);
		FOR(j,60) FOR(i,N) nex[j+1][i]=nex[j][nex[j][i]];
	}
};



FunctionGraph<10010> fg;
int dp[10100][10101];
vector<int> nex[505];
int N2;
vector<int> VV;
int get(int L,int R) {
	if(L>=N2/2) return get(L-N2/2,R-N2/2);
	return dp[L][R];
}

int hoge(vector<int> V) {
	FORR(v,V) v%=N;
	if(V.size()==1) return 0;
	int x,y=V.size();
	FOR(x,y) V.push_back(V[x]);
	VV=V;
	N2=V.size();
	FOR(x,N2) FOR(y,N2/2) dp[x][x+y]=0;
	
	FOR(x,N) nex[x].clear();
	FOR(x,N2) nex[V[x]].push_back(x);
	
	int ma=0;
	
	for(int len=1;len<N2/2;len++) {
		for(x=0;x<N2/2;x++) {
			int y=x+len;
			if(x>=N2/2) {
				dp[x][y]=dp[x-N2/2][y-N2/2];
			}
			else {
				int ret=dp[x+1][y];
				
				auto it=lower_bound(ALL(nex[VV[x]]),x+1);
				while(it!=nex[VV[x]].end()&&*it<=y) {
					
					ret=max(ret,1+get(x+1,*it)+get(*it,y));
					it++;
				}
				dp[x][y]=ret;
			}
		}
	}
	
	FOR(x,N2/2) {
		FORR(e,nex[V[x]]) if(e>x&&e<N2/2) ma=max(ma,dp[x][e]+dp[e][x+N2/2]-1);
	}
	
	return ma;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N*K) {
		cin>>P[i];
		P[i]--;
		fg.E[i]=P[i];
	}
	fg.build(N*K);
	
	int ret=0;
	FOR(i,fg.NG) ret+=hoge(fg.G[i]);
	cout<<ret<<endl;
}

まとめ

途中TLEを繰り返して、最終的に1.98sでギリギリ通った。
計算量は想定解と同じなんだけど、どこで時間かかってるんだろ。