AtCoder ARC #204 : C - Maximize Sum of Mex

時間内に詰め切れず…。
https://atcoder.jp/contests/arc204/tasks/arc204_c

問題

1～Nの順列Pが与えられる。
N要素の整数列Bを作る。その際、クエリとしてB中に含まれる0,1,2の数(A0,A1,A2)が指定される。
Bのスコアをsum(MEX(B[i],B[P[i]]))としたとき、その最大値を求めよ。

解法

Pをfunction graphとみなし、各連結成分の閉路長を考える。
一端Bの各要素を2としたうえで、B[i]=2となった箇所はMEX値に影響を及ぼさないので、そこに0,1をどう配置するかを考える。
ベストはB[i]とB[P[i]]に0と1を交互に配置するようにすることで、MEX値が2となる。
そのため、極力閉路長が2となる連結成分に対し、0,1を交互に配置したい。
ただし極力、閉路内に0を詰め切りたくて、余るのを避けたい。閉路長に0を埋めきれないところがあると、隙間に1を入れてもMEX値を2にできないためである。

あとは0の個数で場合分けする。

• 閉路長が偶数のものの、総長をEとしたとき、A0≦E/2の場合
  • もしいくつかの連結成分を使うとちょうど閉路内に0を1個おきに敷き詰められる場合そうする。あとは隙間に1を1個埋めるごとにMEX値の和を2増やせる。
  • そうでない場合、1を埋めることでMEX値の和を2増やせる箇所が1個へるが、MEX値の和を1増やせる箇所が2個増える。
  • 「ちょうど閉路内に0を1個おきに敷き詰められる場合」はDPで求める。bitsetでも良いし、閉路長のバリエーションがO(√N)個しかないことを用いてもよい。
• それ以上の場合、以下の優先度で0を奇数長の閉路に詰めていく。
  • 0が隣接しないよう、1個おきで奇数長のところに詰める。
  • まだ余る場合、奇数長の閉路1個毎に2が2連続している箇所が1個あるので、うち片方に0を詰める
  • まだ余る場合、長さ1の閉路に0を詰める
  • まだ余る場合、0と0の間に挟まれた2の部分に0を詰める。

あとはMEX値を2,1,0増やせる場所に、優先的に1を詰める。

int N,Q;
int P[303030];

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<301010> fg;
bitset<156464> bs;
int C1[303030];
int C2[303030];
int Y[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>P[i];
		P[i]--;
		fg.E[i]=P[i];
	}
	fg.build(N);
	vector<int> M1;
	bs[0]=1;
	int sum[2]={};
	int ns[2]={};
	FOR(i,fg.NG) {
		if(fg.GS[i]%2==0) {
			bs|=bs<<(fg.GS[i]/2);
		}
		else {
			M1.push_back(fg.GS[i]);
		}
		ns[fg.GS[i]%2]++;
		sum[fg.GS[i]%2]+=fg.GS[i];
	}
	
	FOR(i,sum[0]/2+1) {
		C2[i]=i;
		if(bs[i]==0) {
			C2[i]--;
			C1[i]+=2;
		}
	}
	
	sort(ALL(M1));
	reverse(ALL(M1));
	
	int cur=sum[0]/2;
	
	// 0を1個おきに埋める
	FORR(v,M1) if(v>1) {
		C2[cur+1]=C2[cur];
		C1[cur+1]=C1[cur]+2;
		FOR(i,v/2-1) {
			cur++;
			C2[cur+1]=C2[cur]+1;
			C1[cur+1]=C1[cur];
		}
		cur++;
	}
	
	// 0が2連続の場所が出るように埋める
	FORR(v,M1) {
		C1[cur+1]=C1[cur];
		C2[cur+1]=C2[cur];
		Y[cur+1]=Y[cur]+1;
		if(v>1) {
			C1[cur+1]-=2;
			C2[cur+1]++;
		}
		cur++;
	}
	while(cur<N) {
		C1[cur+1]=C1[cur];
		C2[cur+1]=C2[cur]-1;
		Y[cur+1]=Y[cur]+2;
		cur++;
	}
	
	//FOR(i,N+1) cout<<i<<" "<<C2[i]<<" "<<C1[i]<<" "<<Y[i]<<endl;
	
	
	cin>>Q;
	while(Q--) {
		int N0,N1,N2;
		cin>>N0>>N1>>N2;
		
		int ret=2*N0-Y[N0];
		
		x=min(C2[N0],N1);
		ret+=2*x;
		N1-=x;
		x=min(C1[N0],N1);
		ret+=x;
		
		
		
		cout<<ret<<endl;
		
	}
	
}

まとめ

方向性は合ってたのだが、A,Bで時間を使いすぎたこともあって細かいところが間に合わず。