AtCoder AGC #020 : D - Min Max Repetition

うーむ。
https://agc020.contest.atcoder.jp/tasks/agc020_d

問題

f(A,B)を以下のように定義する。

• "A"をA個、"B"をB個からなる文字列である。
• そのような文字列のうち、同じ文字の連続する回数は最小である。
• さらにそのような文字列のうち、辞書順最小である。

A,B,C,Dが与えられるので、f(A,B)のC～D文字目を求めよ。

解法

2個目の条件における連続階数Cは、二分探索でもよいしceil(max(A,B)/(min(A,B)+1))で1発で求めることもできる。

以下の文字列を考える。
G(A,B,C) := AAA..ABA...ABA... (先頭からAがC個並んだ後Bが1個、を繰り返す文字列)
H(A,B,C) := BAB...BBBAB..BBB (末尾からBがC個並んだ後Aが1個、を繰り返す文字列)
細かい証明はEditorialに任せるとして、F(A,B)はG(A,B,C)のprefixとH(A,B,C)のsuffixを連結した形となる。
問題はG,Hから何文字取るかだが、G(A,B,C)のprefixにおけるAの登場回数を二分探索することでその位置を求めることができる。

GとHを何文字取るかがわかれば、F(A,B)のC～D文字目はそれぞれO(1)で取れるので、O(D-C)で文字列を生成できる。

int Q;
int A,B,C,D;

string hoge(int A,int B,int C,int D) {
	int i;
	int L=(max(A,B)+min(A,B))/(min(A,B)+1);
	
	int na=0;
	for(i=30;i>=0;i--) {
		int nac=na+(1<<i);
		int nb=max(0,(nac-1)/L);
		if(nac>A || nb>B) continue;
		int ma=A-nac;
		int mb=B-nb;
		
		if(mb>1LL*(ma+1)*L) continue;
		na+=1<<i;
	}
	
	
	int p=na+max(0,(na-1)/L);
	string R;
	for(i=C;i<=D;i++) {
		if(i<p) R+='A'+(i%(L+1)==L);
		else R+='B'-((A+B-1-i)%(L+1)==L);
	}
	return R;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	FOR(i,Q) {
		cin>>A>>B>>C>>D;
		cout<<hoge(A,B,C-1,D-1)<<endl;
		
	}
}

まとめ

そういう形になる、ってのがさっと出なかった。