A. Meximum Array
列全体での mex が $c$ であるとき，$b$ の先頭を $c$ にすることは可能ですし，$c$ より大きくすることは不可能です．最初の操作では mex が $c$ になるような $k$ を選ぶことになります．
この際，$k$ はそれを実現するもののうちで最小のものを選ぶとしてよいです．そうでない方法があったとして，最初に選ぶ $k$ だけを小さくすることを考えると証明できます．
B. Peculiar Movie Preferences
入力の中に回文があればそれひとつを選ぶことで条件達成です．以下回文がないとします．特にすべての入力文字列の長さは $2$ または $3$ です．
回文を作るときの両端に置く文字列に注目します： $S=X_1 \cdots X_K$．
$|X_1|$, $|X_K|$ の長さで場合分けをすると，$S$ が回文ならば $X_1X_K$ も回文であることが分かります．よって，$2$ つの結合のパターンだけを考えればよいです．
C. Grid Xor
次のような言い換え問題を説明します．
- $(N,N)$ グリッドがあり，すべてのマスに $0$ が書かれている．
- いくつかの $(i,j)$ を選ぶ．選んだマスの $4$ 近傍が存在すればその近傍の状態の $0,1$ が toggle される．
- すべてのマスに $1$ が書かれた状態にせよ．
これが達成できたとき，選んだマスに書かれた数全体の XOR が答となります．
目標のマス目の状態が作れるとき，最初の行をひとつも選ばないような操作が存在することが証明できます．次のような $n$ 通りの操作パターンを $v_1,\ldots,v_n$ とします（1 と書かれている場所を選ぶ）．
100000 010000 101000 010100 001010 000101
010000 101000 000100 100010 010001 001000
001000 010100 100010 000001 100000 010001
000100 001010 010001 100000 000001 100010
000010 000101 001000 010001 100010 000100
000001 000010 000101 001010 010100 101000
するとこれはマスの状態を変化させません．ある操作があるときにこれらを使って先頭の操作を全部消すことができるのでよいです．ここから作れるパターン数が，先頭行を使わない操作からできる $2^{n^2-n}$ パターンであることも分かります（そのような操作の結果が相異なることはすぐにわかる）．
操作で作れるパターンの特徴づけもできています．任意の操作は $v_i$ に $1$ が書かれた場所のうち偶数箇所を toggle します．任意の $v_i$ について，それに $1$ が書かれた個数が偶数個であるようなパターンは $2^{n^2-n}$ 個しかありません．
これで，作れるパターンについての必要十分条件，および，作れるパターンはすべて先頭行を使わずに作れることが分かりました．
D2. Game on Sum (Hard Version)
$k=1$ としてよいです．$\dp[i][j]$ を，Bob が $i$ 回の足し算と $j$ 回の引き算を残している場合の答とします．$i=0$ の場合と $j=0$ の場合が自明です．
$i,j>0$ の場合，Alice は $x\in [0,1]$ を選び，$\min(\dp[i-1][j]+x,\dp[i][j-1]-x)$ を最大化することになります．$x$ を任意に選べることにすれば，この最大値は $(\dp[i-1][j]+\dp[i][j])/2$ です．
実はこれでよいです．$\dp[i][j]=(\dp[i-1][j]+\dp[i][j-1])/2$ という規則で dp テーブルを作ったときに，$|\dp[i-1][j]-\dp[i][j-1]|\leq 1$ となることが帰納的に言えるからです．よって，$\dp[i][j]=(\dp[i-1][j]+\dp[i][j-1])/2$ という漸化式を処理すればよいことになります．
これは $2^{i+j}\dp[i][j]=2^{i+j-1}\dp[i-1][j]+2^{i+j-1}\dp[i][j-1]$ と変形できます．よって $\dp[i][j]$ の代わりに $\mathrm{DP}[i][j]=2^{i+j}\dp[i][j]$ を考えると，グリッドパスを数え上げる式と同じになって，$i=0,j=0$ の初期値の寄与が適当な二項係数でかけることが分かります．
E. Groceries in Meteor Town
まず変更クエリを無視して考えます．
求値クエリで来る点 $x$ と，アクティブな頂点全体を合わせて $S$ とします．クエリは次のように言い換えられます．
- 辺重みの小さい辺から順にマージしていったときに，$S$ 全体が連結になるのは最後にどの辺をマージした瞬間ですか？
マージ仮定の木を作って，$S$ に含まれる点のうち，dfs 順で最初の点と最後の点の lca を求めればよいことになります．
結局，マージ仮定の木を作っておいて，その木における dfs 順の最初の点と最後の点が何かが分かるようにすればよいことになります．
F. Spaceship Crisis Management
比較的やるだけではありますが，大変です．
方向ベクトルとして可能なものが $O(n+q)$ 通りしかないことを利用します．
- クエリ点から原点に向かうベクトル（壁に一度もぶつからずに原点に到達しうる方向）
- 壁の端点から原点に向かうベクトル（最後にぶつかる壁から原点に到達する方向）
これらそれぞれについて，$O((n+q)\log n)$ 時間で解けばよいです．
方向ベクトルを固定すると，あるクエリ点または壁から出発した場合に次にぶつかる壁が分かります．この関係で DAG を作って，トポロジカル逆順にそこから原点に到達可能かを決定できます．
「次にぶつかる壁」を高速に求める部分が問題です．
適当な回転により，私は方向ベクトルが $x$ 軸負方向になるようにして考えました．$y$ 昇順に平面操作をして，線分の追加削除を行いながら，ある点の左側にある最寄りの線分の検出を行っていけばよいです．
なお方向ベクトルの候補はすぐにわかるのは $2n+q$ 通りですが，線分の端点から出る方向と線分とのなす角で枝狩りすれば高々 $n+q$ 通りになり，この枝狩りは実行時間に結構影響があるようです．
