A. Row GCD
$a_0+b_j$ と，$a_i-a_0$．
B. Glass Half Spilled
$k$ 個選んだときの $\sum a, \sum b$ だけが重要です．dp[k][sum a] = max (sum b) という dp でできます．
C. Latin Square
(row,column,value) という $3$ つ組の集合を考えます．操作は各成分をシフトしたり，2 つの成分を入れ替えたりという操作になります．
D. Flip and Reverse
それぞれの文字を +1, -1 に置き換えて累積和の折線を考えると，$y$ 座標の等しい場所を選んで左右対称移動するという操作になります．各 [y,y+1] の間を結ぶ線分の個数は操作不変量で，逆にそれが等しい 2 つの文字列は変換可能であることが手前から見ればわかります．
E. Nim Shortcuts
実験するとだいたいの形が分かるし証明も難しくない．
入力の $(x,y)$ 以外の敗北場所を考える．各行に高々ひとつで，基本的には $(x+i,y+i)$ という対角に並ぶ形になる．$(x,y’)$ や $(x’,y)$ ($x'<x,y'<y$) などに入力の $(x,y)$ があるとその行や列は飛ばすという形になる．
敗北条件は，$(x,x+a)$, ($l\leq x<r$) という 3 つ組 $(l,r,a)$ の列として書けるのでこれを前計算する．
F. Range Diameter Sum
分割統治を考える．それぞれの中心と半径を考える．中心と半径を $(v,r)$ と書く．
区間の左側，右側でそれぞれとる点を増やしていったときの中心，半径を前計算しておきます．辺の中点にあたる頂点を考えておくと実装しやすくなります．
$(v_1,r_1)$ と $(v_2,r_2)$ のマージがどうなるかが問題です．これは結論としては $d= dist(v_1,v_2)$ として，
- $d < r_1-r_2$ のとき：半径 $r_1$．
- $d < r_2-r_1$ のとき：半径 $r_2$．
- それ以外：半径 $(r_1+r_2+d)/2$．
となることが分かります．（平面図形の円の中心と半径を考えるとやや予想しやすいか）
右側でとる頂点数を増やしたとき，これらの境界は尺取り法で求められます．境界が分かると $r_1,r_2$ の和は適当な累積和でとれるので，問題は $d$ の和を求める部分です．
結局これは次のようなクエリ処理を $O(N\log N)$ 回行えればよいということになります：
- 頂点の多重集合 $S$ を管理せよ．$S$ に点の追加や削除が来る．
- $v$ が与えられるので，$\sum_{s\in S} \mathrm{dist}(v,s)$ を求める．
これは static top tree の dp でできます．$\sum_{s_1,s_2\in S} \mathrm{dist}(s_1,s_2)$ が求まるようにしておけば，求める和は $S$ に $v$ を追加すると和がどう変わるかと同じことなのでこれで大丈夫です．
重心分解による方法もありますが，私の雑な実装では static toptree の方が高速でした．
