A. Slimes on a Line
大小順は保たれるので，min, max を合流させればよいことになります．
B. Absolute Cinema
$a_i\leq b_i$ になるようにスワップしても損しないことが分かります．
C1. We Be Flipping (Easy Version)
全部負にできます．右端から順に見て，その時点で（つまりそれまでの操作を考慮して）正だったら操作対象にする．とすればよいです．
C2. We Be Flipping (Hard Version)
操作しない場合：略．
一度でも操作するインデックスの最大値を $i$ とすれば，$i$ は初期状態正であることが必要で，最終的に負になります．
$i$ の左側は全部正にできます．$[0,i-1]$ に対して C1 の方法ですべて負にしたあとで $i$ を操作すればよいです．
このような $i$ について全探索して一番良いものを選びます．
D. Me When Median Problem
二分探索判定問題を考えます．$0,1$ 列してよいです．
$00, 01, 11$ の $3$ 種と見なして演算を考えると，$01$ は単位元になります．$01$ を無視して $00, 11$ に対する何かと思います．
AB 文字列があって，AA は A に，BB は B に，AB は消せる，BA は消せる．という感じの操作で最後に A を残したいとなります．
最初に BBBB 部分を圧縮し，その上で A の個数が B の個数より大きいというのが条件です（十分性の証明は帰納法など）．
E. Deconstruction Tree
$n$ は消えることはありません．$n$ を根として根付き木にします．
$S$ に追加する頂点番号は，単調増加です．$S=(v_1,v_2,\ldots)$ が実現できる条件を考えます．$v_1$ は固定です．
$v\in S$ であるとき，$v$ は subtree 内で最大であることが必要です．
$\ldots,v,w,\ldots$ のようになっていて $w$ が根でないといます，$v$ が葉である間に $w$ の subtree を消さないといけないので，$sub(w) < v < w$ が必要です．これは十分条件でもあります．
これで適当に実装すると WA が返ってきてしまいました．$w=n$ に相当する何かについて特殊処理が必要っぽくて，これをあやふやなまま雑に実装したら成功しました．
F. Load Unbalancing
$a_i$ にアイテム，$b_j$ に箱などの用語を使います．
「全部のアイテムを使い切る必要はない」としてもよいです．最大値に到達したら終了することにして，最後のアイテムを固定して解きます．さらに目標値を $ANS$ を固定した二分探索を考えます．
$a_i$ が最後のアイテムだとして，これを置く直前の状態で，すべての箱が $ANS-a_i$ 以上になっていないといけません．これは実は必要十分条件です．
この条件だと他の箱に，最小値を超えているのに操作を余分にしている可能性がありそうですが，余分な操作をして必要条件を満たせるなら，余分な操作をキャンセルすれば十分条件も満たせます．結局，次を解けばよいです：最後のアイテムを避ける．他のアイテムですべての箱を $ANS-a_i$ 以上にできるかどうかを判定．
「使ったアイテム集合」「箱の個数」などを状態とする dp を考えそうになりましたが，これは単に「使ったアイテム集合」だけを状態として，「箱の個数，最後の箱の容量の組」などを最適化する dp にできます．
これで，最後のアイテムと目標 ANS を固定したときの二分探索判定問題が $O(N\cdot 2^{N})$ 時間になります．
ここにアイテム全探索と ANS 二分探索を入れて，$N\times \log (\sum a_i)$ 的な計算量で解きました．ただし，アイテム全探索順をシャッフルするテクニックで，期待値 $(N+\log N\log \sum a_i)$ 倍程度になっていると思います．
よく考えると，最後のアイテムは最大値のアイテムに限定してよいですね．これは（上の必要十分条件を得たあと）単純に $2$ 個入れ替える議論をすれば分かる．
G. Load Unbalancing
各町への最速到達時刻 $day[i]$ を求めておきます．
ある町で「とどまる」という操作をすることがある場合，その町には $day[i]$ に到達しているとしてよいです．あまり厳密にやってないけど普通の exchange argument で示せるはず．
これを信じると，「dp[i]：町 $i$ に day[i] に到達する場合の…」という $N$ 個の値を計算すれば勝ち，という解法の枠組みができます．
あとは CHT を頑張る．ということになります．
day について昇順に計算しようとします．するとこれは始点 $s$ を基準として，左右に区間を広げていくという順に計算されることになります．「左側に町を追加するためのデータ構造」「右側に町を追加するためのデータ構造」をそれぞれ持てばよいことになります．
例えば右側に町を追加する場合，$(i,day[i]) \to (j,day[j])$ が到達可能な $i$ 全体に対して $1$ 次関数を max という感じの計算になります．もうひとつ重要なこととして，「到達可能な $i$ 全体」は単調増加になってくれます．
したがって 普通に incremental な CHT という形になります．
H. Wowee Binary String
目標文字列 $S$ を固定したときの判定問題を考えます．”?” がないなら簡単で，とにかく最速にとっていくとよいです．
つまり，$S_i$ まで作った状態から、「1 を偶数個はさんで次に $S_{i+1}$ が登場する位置」を探し，そこを使うというようにします．最速完成した位置から最後に suffix が全消しできるかを判定ということになります．
なぜこれでいいかというと，最速完成より遅い位置で完成したとしても，使う $1$ の個数の偶奇が固定なので，最後の suffix 全消し条件に影響しないからです．結局 “?” がなければ $O(N)$ 時間で解けてしまいます．
“?” があると，最速完成だけではまずいはずです．最速完成させると suffix に $1$ が奇数個になってしまうが，何らかの別方法で完成させると suffix に $1$ が偶数個残るようにできる．ということがありえます．
そこで，判定問題の状態を次のように修正します．
- 最後に使った文字が $p$ 番目であるとする．
- $[0,p]$ に含まれる “1” の個数（”?” は数えない）の parity を $p$ の parity と呼ぶ．
- parity 奇数の位置での最速完成と，parity 偶数の位置での最速完成の組を状態とする．
あとは topological 順に気を付けたり，最速完成位置が存在しない場合に気を付けたりしながら dp すればよいです．
I. The Endians
まだ．
