AtCoder Grand Contest 020D: Min Max Repetition

https://agc020.contest.atcoder.jp/tasks/agc020_d

お気持ちそのままが解法ですが、実装がめんどくさすぎる…。1発ACだけど詰めるのにすごい時間かかった。
A>Bとします。B<=Aの場合もだいたい同じです。

まず文字が何個まで連続できるかを求めます。これは少し考えればfloor( (A+B)/(B+1) )であることがわかります。これをUとおきましょう。

だいたい同じような文字列の繰り返しになってなるべくAを前に持ってくればいいんだろうなという感覚から考えて、
N,M,α,β,Lをそれぞれ0以上の自然数とすると、答えは
(A*U+B)*N+(A*α)+(B*β)+(A+B*U)*M+(A*L)となることが証明できます。
0<α<=Uの条件からNを二分探索で求め、M,α,β,Lも確定します。後は文字列を正しく出力すればいいです。

A,Bが大きいときどうだろうと考えられたのは良かったですね。極限状態を考えるとうまく行くことが多いのに最近気づきました。

int Q;
ll A, B, leftb, rightb;
ll U, N, M, alpha, beta, L;

void pre() {
	U = (A + B) / (B + 1);
	if(A == B) {
		N = B; M = 0; alpha = 0; beta = 0; L = 0;
		return;
	}
	if(A - U * B > 0) {
		N = B;
		M = 0;
		alpha = 0;
		beta = 0;
		L = A - U * B;
	}
	else {
		ll lv = 0, rv = (A + B) / (U + 1) + 10;
		while(rv - lv > 1) {
			ll m = (lv + rv) / 2;
			if(A - (U * m + (B - 1 - m) / U) > 0) lv = m;
			else rv = m;
		}
		N = lv;
		M = (B - 1 - N) / U;
		alpha = A - (U * N + M);
		beta = B - (N + U * M);
		L = 0;
	}
}

string F(ll lv, ll rv) {
	string res = "";
	for(ll i = lv; i < rv; i++) {
		if(i % (U + 1) == U) res += 'B';
		else res += 'A';
	}
	return res;
}

string G(ll lv, ll rv) {
	string res = "";
	for(ll i = lv; i < rv; i++) {
		if(i < alpha) res += 'A';
		else res += 'B';
	}
	return res;
}

string H(ll lv, ll rv) {
	string res = "";
	for(ll i = lv; i < rv; i++) {
		if(i % (U + 1) == 0) res += 'A';
		else res += 'B';
	}
	return res;
}

string I(ll lv, ll rv) {
	string res = "";
	for(ll i = lv; i < rv; i++) {
		res += 'A';
	}
	return res;
}

string pre2() {
	ll bd0 = 0; ll bd1 = (U + 1) * N; ll bd2 = (U + 1) * N + alpha + beta;
	ll bd3 = (A + B - L); ll bd4 = A + B;
	// debug(U, N, M, alpha, beta, L);
	// debug(bd0, bd1, bd2, bd3);
	string res = "";
	res += F(max(bd0, leftb) - bd0, min(bd1, rightb) - bd0);
	res += G(max(bd1, leftb) - bd1, min(bd2, rightb) - bd1);
	res += H(max(bd2, leftb) - bd2, min(bd3, rightb) - bd2);
	res += I(max(bd3, leftb) - bd3, min(bd4, rightb) - bd3);
	return res;
}

string sub_solve() {
	bool swaped = false;
	if(B > A) {
		swaped = true;
		swap(A, B);
		leftb = (A + B - 1) - leftb;
		rightb = (A + B - 1) - rightb;
		swap(leftb, rightb);
		rightb++;
	}
	else rightb++;
	pre();
	string res = pre2();
	if(swaped) {
		reverse(all(res));
		rep(i, 0, sz(res)) {
			if(res[i] == 'A') res[i] = 'B';
			else res[i] = 'A';
		}
	}
	return res;
}

void solve() {
	cin >> Q;
	while(Q--) {
		cin >> A >> B >> leftb >> rightb; leftb--; rightb--;
		cout << sub_solve() << "\n";
	}
}