A - Mex Game

Hint 1

There is an optimal strategy where Alice chooses $x$ such that $S_x$ is B and Bob chooses $x$ such that $S_x$ is A.

Editorial → https://atcoder.jp/contests/agc063/editorial/6880

---

B - Insert 1, 2, 3, …

Hint 1

First, let us consider a fast way to determine if a sequence is generatable. I think it is simpler to focus on the leftmost $1$.

Hint 2

The decision problem of whether a given sequence is generatable can be solved by scanning the sequence backward using a stack.

Hint 3

Counting can be done either by fixing $L$ and finding the number of corresponding $R$, or by fixing $R$ and finding the number of corresponding $L$.

Editorial → https://atcoder.jp/contests/agc063/editorial/6882

---

C - Add Mod Operations

Hint 1

Clearly, it is necessary that $A_i = A_j \implies B_i = B_j$. The procedure can be constructed based on this necessary condition.

Hint 2

We can set $y = x + \max(A)$ to translate all points and then change only the maximum value to $0$.

Editorial → https://atcoder.jp/contests/agc063/editorial/6884

---

D - Many CRT

Hint 1

Let us reduce the problem to the case $\gcd(c,d)=1$.

Hint 2

If $b$ is a multiple of $d$, then it is useful to divide $x\equiv a+bk$ by $c+dk$ as polynomials of $k$. In this problem, $b$ is not necessarily a multiple of $d$, but we can do the same by considering $dx$ instead of $x$.

Hint 3

When $L$ is the least common multiple of $\{c+kd\mid 0\leq k\leq N-1\}$, the condition can be transformed into the form $dx\equiv \mathrm{constant}\pmod{L}$. Although $L$ is generally huge, we can find the prime factorization of $L$ using a method like interval sieve. By computing the remainder of $L$ divided by $d$ or $998244353$, we can find the smallest non-negative $x$.

Editorial → https://atcoder.jp/contests/agc063/editorial/6885

---

E - Child to Parent

Hint 1

If we ignore the computational complexity, we can solve this bottom-up with a simple tree DP. All the necessary computations can be expressed in polynomial forms, but the number of coefficients needed for the computation would be very large if we simply use polynomials.

Hint 2

By performing a variable transformation like considering $f(x+1)$ instead of a polynomial $f(x)$, you can reduce the number of coefficients needed for the computation.

Editorial → https://atcoder.jp/contests/agc063/editorial/6886

---

F - Simultaneous Floor

Hint 1

See a pair of two numbers as a lattice point on the coordinate plane, and consider the operations graphically. It is also simpler to think of the inverse of the operation.

Hint 2

When the point \(B\) is in the first quadrant, then for any \(k\geq 1\), the set of all \(A\) such that \(B\) can be reached from \(A\) with \(k\) operations can be expressed as \(\{(x,y)\mid l_k<y/x<r_k\}\) using certain rational numbers \(l_k, r_k\).

Editorial → https://atcoder.jp/contests/agc063/editorial/6887