A. Marisa Steals Reimu’s Takeout
極小な作り方は，「$0$」「$12$」「$111$」「$2222$」です．
「$111$,$222$」は「$12$,$12$,$12$」にした方が得です．したがって $111$, $222$ は両立しないとしてよいです．
ここから，「$12$」を可能な限りとってしまうのが最適だと分かります．
B. Remilia Plays Soku
$n\leq 3$ は $1$ 手で詰み．それ以外のやつは，初期状態の距離 $+k$ です．
それだけ逃げられることは，隣接してから逃げ始めることで分かります．
それ以上は逃げられないことは，追いかける側が初期状態の最短路方向に進み続けることで分かります．
C2. Cirno and Number (Hard Version)
「$b\leq a$ となる最大の $b$」「$a\leq b$ となる最小の $b$」をそれぞれ適当な桁 dp で求めればよいです．後者は $d=(0)$ のときに存在しないことに注意．
D. Sanae, Cross and Color
まず，座圧して $x$ 座標の種類が $0,1,\ldots,H-1$，$y$ 座標の種類が $0,1,\ldots,W-1$ となるようにします．
すると，$a=0,1,\ldots,H$ および $b=0,1,\ldots,W$ に対して $x$ 座標の分割 $[0,a),[a,H)$ と $y$ 座標の分割 $[0,b),[b,W)$ をとれば，これらはすべて互いに区別可能です．このうちで $4$ 領域とも空にならないものを数えます．
$x$ 座標境界を決めると，$x$ の小さい側・大きい側それぞれでの $y$ 座標の $\min,\max$ から答が計算できます．
E2. Amanojaku and Sequence (Hard Version)
作業量だけばかみたいに多い解法になりました．とにかく作業をたくさんすれば解けるというタイプだとは思います．
- $0\leq A[i]$ に対する $A[i]^2(R-i)$ の和
- $A[i]=-1$ に対する $(R-i)$ の和
- $i<j,0\leq A[i],0\leq A[j]$ に対する $A[i]A[j](R-j)$ の和
- $i<j,0\leq A[i],A[j]=-1$ に対する $A[i](R-j)$ の和
- $i<j,A[i]=-1,0\leq A[j]$ に対する $A[j](R-j)$ の和
- $i<j,A[i]=-1,A[j]=-1$ に対する $(R-j)$ の和
これらに何らかの係数を足す．ということになります．
まずこれらの和の求め方ですが，$\sum_{i<j} x[i]y[j](R-j)$ のタイプの和になっています．
$\sum_{i<j}x[i]y[j]$ や $\sum_{i<j}x[i]y[j]j$ をセグ木に持たせればよいです．セグ木のひとつのノードに $14$ 個くらいの modint を持って熱烈実装でできます．
「何らかの係数」について．
例えば $A[i]=-1, 0\leq A[j]$ とします．これの係数は $-1$ の個数を $q$ として，
$$\sum_{k}kx^k\cdot (1/(1-x))^{q-1}$$
です．$\sum_{k}kx^k=\frac{x}{1-x}$ などから $[x^a](1-x)^b$ の形の計算に帰着できます．他の係数も同様です．
F. Momoyo and the Network
$1/3$ 重心分解して，次の状況に帰着します．
- 赤い点と青い点を結ぶパスについて調べる．これらを結ぶと根を通ることは分かっている．
長さ $k$ というのは深さの和が $k$ ということです．各点に対して，根から見たその方向の subtree size や，根からのパスの途中で切り離される成分の大きさの min を計算しておけば，おおよそ次のような処理になります．
- ペア $(a_i,b_i)$ とペア $(c_j,d_j)$ がたくさん与えられる．$\min(a_i,c_j,S-b_i-d_j)$ を最大化せよ．
これを二分探索で処理して，私の解法は $\log^2$ 的な計算量です．
乱択二分探索を上手く組み合わせれば高速化できるはず．結局二分探索するならはじめから答で二分探索した方が良かったかもしれないと後から思いました．
