kmjp's blog

競技プログラミング参加記です

AtCoder ABC #273 (パナソニックグループプログラミングコンテスト2022) : Ex - Inv(0,1)ving Insert(1,0)n

ARC

結構コード量多いな。
https://atcoder.jp/contests/abc273/tasks/abc273_h

問題

整数対の列Aを考える。初期状態ではA=[(0,1),(1,0)]である。
Aに対し、以下の処理を考える。

  • 隣接する2要素(a,b),(c,d)を1組選び、間に(a+c,b+d)を挿入する。

整数値の対の列Sに対し、f(S)をAにSの全要素を含むための最小処理回数と定義する。
ただし、Sのうち上記手順で生成できない要素がある場合は、f(S)=0とする。

今整数対の列Sが与えられる。その部分列S[l,r]に対しf(S[l,r])の総和を求めよ。

解法

上記手順はStern-Brocot Treeの生成手順そのものである。
Stern-Brocot Treeは互いに素でない整数対は生成できないので、まずSを互いに素でない整数対で分割し、以下分割した数列毎に解を考える。
入力値すべてを含む最小のStern-Brocot Treeを生成する。
また、その過程で、S中の要素に対応する木のノードに、S中のindexを持つことにしよう。

各ノードが生成される条件は、部分列S[l,r]を取ったときに、ノードのSubtree内のノードに含まれるindexを一つも持たないことである。
そこで、マージテクの要領で、葉ノードから順に、「そのノードを生成しなければいけなくなるindexの集合」を計算していこう。
同時に、区間[l,r]のうち前indexの集合に含むものを持たない組み合わせの数も更新し、ノード毎に解に計上する。

最後の問題は、整数対の値によっては、木の深さが非常に深くなることである。
そこは、index集合が変化しない範囲で、二分探索の要領で一気にStern-Brocot Treeの生成手順を繰り返し、ノードを明に作らないようにするとよい。

int M;
ll N;
ll ret;
vector<pair<pair<ll,ll>,int>> C;
int nex;

ll dp[1505050];
set<int> Vs[1505050];

const ll mo=998244353;

bool cmp2(pair<ll,ll> L,pair<ll,ll> R) {
	return (__int128)L.first*R.second<(__int128)L.second*R.first;
}

bool cmp(pair<pair<ll,ll>,int> L,pair<pair<ll,ll>,int> R) {
	if(L.first.first*R.first.second<L.first.second*R.first.first) return 1;
	if(L.first.first*R.first.second>L.first.second*R.first.first) return 0;
	return L.second<R.second;
}

int dfs(int L,int R,pair<ll,ll> VCL,pair<ll,ll> VCR) {
	if(L>R) return -1;
	int cur=nex++;
	dp[cur]=0;
	Vs[cur].clear();
	pair<ll,ll> VCM={VCL.first+VCR.first,VCL.second+VCR.second};
	
	if(cmp2(VCM,C[L].first)) {
		int step=0;
		int i;
		for(i=29;i>=0;i--) {
			VCM.first=VCL.first+(step+(1LL<<i))*VCR.first;
			VCM.second=VCL.second+(step+(1LL<<i))*VCR.second;
			if(cmp2(VCM,C[L].first)) step+=1LL<<i;
		}
		
		
		VCM.first=VCL.first+(step)*VCR.first;
		VCM.second=VCL.second+(step)*VCR.second;
		int C=dfs(L,R,VCM,VCR);
		(ret+=(step-1)*(1LL*N*(N+1)/2%mo-dp[C]))%=mo;
		dp[cur]=dp[C];
		swap(Vs[cur],Vs[C]);
	}
	else if(cmp2(C[R].first,VCM)) {
		int step=0;
		int i;
		for(i=29;i>=0;i--) {
			VCM.first=(step+(1LL<<i))*VCL.first+VCR.first;
			VCM.second=(step+(1LL<<i))*VCL.second+VCR.second;
			if(cmp2(C[R].first,VCM)) step+=1LL<<i;
		}
		
		VCM.first=(step)*VCL.first+VCR.first;
		VCM.second=(step)*VCL.second+VCR.second;
		
		int C=dfs(L,R,VCL,VCM);
		(ret+=(step-1)*(1LL*N*(N+1)/2%mo-dp[C]))%=mo;
		dp[cur]=dp[C];
		swap(Vs[cur],Vs[C]);
	}
	else {
		pair<pair<ll,ll>,int> TV={VCM,0};
		int M=lower_bound(C.begin()+L,C.begin()+R+1,TV,cmp)-C.begin();
		int LE=M;
		int pre=-1;
		while(M<=R&&C[M].first==VCM) {
			(dp[cur]+=1LL*(C[M].second-pre-1)*(C[M].second-pre)/2)%=mo;
			pre=C[M].second;
			Vs[cur].insert(pre);
			M++;
		}
		(dp[cur]+=1LL*(N-1-pre)*(N-pre)/2)%=mo;
		
		int i;
		FOR(i,2) {
			int C;
			if(i==0) C=dfs(L,LE-1,VCL,VCM);
			else C=dfs(M,R,VCM,VCR);
			if(C==-1) continue;
			if(Vs[cur].size()<Vs[C].size()) {
				swap(dp[cur],dp[C]);
				swap(Vs[cur],Vs[C]);
			}
			FORR(v,Vs[C]) {
				auto it=Vs[cur].lower_bound(v);
				int a,b;
				if(it==Vs[cur].begin()) {
					a=-1;
					b=*it;
				}
				else if(it==Vs[cur].end()) {
					a=*--it;
					b=N;
				}
				else {
					b=*it;
					a=*--it;
				}
				(dp[cur]-=1LL*(b-a-1)*(b-a)/2)%=mo;
				(dp[cur]+=1LL*(b-v-1)*(b-v)/2)%=mo;
				(dp[cur]+=1LL*(v-a-1)*(v-a)/2)%=mo;
				Vs[cur].insert(v);
			}
			(dp[cur]=dp[cur]%mo+mo)%=mo;
		}
		
	}
	(ret+=1LL*N*(N+1)/2-dp[cur])%=mo;
	
	return cur;
}


void hoge(vector<pair<ll,ll>> C3) {
	N=C3.size();
	if(N==0) return;
	vector<pair<pair<ll,ll>,int>> C2;
	int i;
	FOR(i,N) C2.push_back({C3[i],i});
	sort(ALL(C2),cmp);
	C=C2;
	int L=0,R=C.size()-1;
	while(L<C.size()&&C[L].first.first==0) L++;
	while(R>=0&&C[R].first.second==0) R--;
	if(L>R) return;
	nex=0;
	pair<ll,ll> SL={0,1};
	pair<ll,ll> SR={1,0};
	dfs(L,R,SL,SR);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M;
	vector<pair<ll,ll>> C;
	FOR(i,M) {
		cin>>x>>y;
		if(__gcd(x,y)!=1) {
			hoge(C);
			C.clear();
		}
		else {
			C.push_back({x,y});
		}
	}
	hoge(C);
	
	cout<<(ret%mo+mo)%mo<<endl;
	
	
}

まとめ

Stern-Brocot Treeまではすぐ思いついたものの、複数回の生成ステップをまとめて行う点に考えが至らなかった…。