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"; } }