A - Mex Game

Hint 1

Alice は $S_x$ が B であるような $x$ を，Bob は $S_x$ が A であるような $x$ を選ぶという最適戦略があります．

解説 → https://atcoder.jp/contests/agc063/editorial/6737

---

B - Insert 1, 2, 3, …

Hint 1

まずは，列が生成可能であるかを高速に判定する方法を考えましょう．「$1$」のうち最も後ろにあるものに注目するのが簡潔だと思います．

Hint 2

与えられた列が生成可能であるかの判定問題は，スタックを使って後ろにある要素から順に走査していくことで解けます．

Hint 3

数え上げは，$L$ を固定して $R$ の個数を求めるという方法でも，$R$ を固定して $L$ の個数を求めるという方法でも計算できます．

解説 → https://atcoder.jp/contests/agc063/editorial/6741

---

C - Add Mod Operations

Hint 1

明らかに $A_i = A_j \implies B_i = B_j$ が成り立つことが必要です．この必要条件のもと手順を構築することができます．

Hint 2

$y = x + \max(A)$ とすると，すべての点を平行移動したあと，最大値のみを $0$ に変化させられます．

解説 → https://atcoder.jp/contests/agc063/editorial/6738

---

D - Many CRT

Hint 1

$\gcd(c,d)=1$ の場合に帰着しましょう．

Hint 2

$b$ が $d$ の倍数ならば，$k$ の多項式として $x\equiv a+bk$ を $c+dk$ で割るという式変形が有効です．本問題では $b$ が $d$ の倍数とは限らないですが，$x$ の代わりに $dx$ を考えることで同様のことが可能になります．

Hint 3

$L$ を $\{c+kd\mid 0\leq k\leq N-1\}$ の最小公倍数とするとき，条件は $dx\equiv \mathrm{constant}\pmod{L}$ の形に変形できます． $L$ は一般には巨大ですが，区間篩のような手法で $L$ の素因数分解を求めることができます．$L$ を $d$ や $998244353$ で割った余りを計算することで，非負最小の $x$ を計算できます．

解説 → https://atcoder.jp/contests/agc063/editorial/6739

---

E - Child to Parent

Hint 1

計算量を無視すれば，子から親に向かって順に計算する簡単な木 dp で解くことができます．必要な計算はすべて多項式を用いて表せますが，単純に多項式にするだけでは計算に必要な係数の個数が非常に大きくなってしまいます．

Hint 2

多項式 $f(x)$ の代わりに $f(x+1)$ を考えるというタイプの変数変換をすることで，計算に必要な係数の個数を減らすことができます．

解説 → https://atcoder.jp/contests/agc063/editorial/6740

---

F - Simultaneous Floor

Hint 1

\(2\) 数の組を座標平面上の格子点と見なし，操作を図形的に考えましょう．さらに「操作の逆」について考えると簡潔になります．

Hint 2

点 \(B\) が第 1 象限内にあるとき，任意の \(k\geq 1\) に対して，「\(B\) へ \(k\) 回の操作で到達可能」であるような \(A\) 全体は，ある有理数 \(l_k, r_k\) を用いて \(\{(x,y)\mid l_k<y/x<r_k\}\) と表すことができます．

解説 → https://atcoder.jp/contests/agc063/editorial/6742