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