AtCoder ABC #312 (ユニークビジョンプログラミングコンテスト2023 夏) : Ex - snukesnuke

くだらないミスで賞金圏外になったの残念だな。
https://atcoder.jp/contests/abc312/tasks/abc312_h

問題

N人の人の名前を決めることを考える。
各人、文字列S[i]を自分の名前にしてほしいと考えている。
以下のように各人の名前を決めるとき、それぞれS[i]を何回繰り返した物となるか。

• i番の人は、S[i]を1回以上繰り返した文字列のうち、i番より手前の人の名前と重複しない最短の文字列を名前とする。

解法

まず、S[i]が周期性を持つ文字列である可能性を考え、最短の周期を求めて「S[i]はS'[i]をR[i]回繰り返した物」というように言い換えよう。
S'[i]が異なる人同士は、以後名前が衝突することはないので、以降S'[i]が一致する人同士をまとめて考える。

R[i]が一致する人がたくさんいると、名前の衝突を繰り返してしまうので、同じR[i]を持つ人に対し、過去何回繰り返した結果が登場済みかメモしておこう。
それ以外に、(R[i]を問わず)S'[i]を何回繰り返した物が使用済みか保持しながら空いている繰り返し回数を探索していこう。

int N;
string S[202020];
ll R[202020];
ll ret[202020];

using VT = string;
map<string,vector<int>> M;



vector<int> Zalgo(VT s) {
	vector<int> v(1,s.size());
	for(int i=1,l=-1,r=-1;i<s.size();i++) {
		if(i<=r && v[i-l]<r-i+1) v.push_back(v[i-l]);
		else {
			l=i; r=(i>r)?i:(r+1);
			while(r<s.size() && s[r-i]==s[r]) r++;
			v.push_back((r--)-l);
		}
	}
	v.push_back(0);
	return v;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>S[i];
		auto Z=Zalgo(S[i]);
		R[i]=1;
		for(j=1;j<S[i].size();j++) if(S[i].size()%j==0&&j+Z[j]==S[i].size()) R[i]=max((ll)R[i],(ll)S[i].size()/j);
		S[i]=S[i].substr(0,S[i].size()/R[i]);
		M[S[i]].push_back(i);
	}
	FORR2(a,V,M) {
		map<ll,ll> pre;
		set<ll> S;
		FORR(v,V) {
			r=R[v];
			ll cur=pre[r]+r;
			while(S.count(cur)) cur+=r;
			S.insert(cur);
			pre[r]=cur;
			ret[v]=cur/r;
		}
		
	}
	FOR(i,N) cout<<ret[i]<<" ";
	
}

まとめ

Gが簡単目だったのは、Exを600ptにするためだったのかな。