A. LRC and VIP
種類数が $1$ ならば不可能．そうでなければ，片方を max だけにすれば条件を満たします．
B. Apples in Boxes
負ける瞬間は次のどちらかしかないです．
- 初手
- すべての $a_i$ が $0$ になった場合．
なぜならば，$\max(a)-\min(a)\leq k$ が成り立っていて $\max(a)\geq 1$ ならば，最大値を選ぶ手が合法になるからです．
初手生き残れるかは単純に判定．すべて $0$ になったときは $\mathrm{sum}(a)$ を見れば手番が決まります．
C. Maximum Subarray Sum
空欄をすべて $-\infty$ で埋めた場合を考えます．この状態から適当な空欄に対するインクリメントを繰り返すことですべての空欄を $\infty$ まで増やしていきます．このとき，max subarray sum は $1$ より大きく増えることはありません．なので，初期状態と終状態の間に $k$ があれば必ず達成できます．そうでなければ明らかに不可能です．
これを二分探索すればよいです．実際にはインクリメントはひとつの空欄を対してやるだけで max subarray sum は $\infty$ になるので，一要素に対する二分探索で十分です．
D. Apple Tree Traversing
計算量を問わなければ，「頂点番号の辞書順が最大の直径を見つける」「それを消す」「残った連結成分ごとに解く」を繰り返せばよいです．
頂点番号を含めて最大の直径をとるには，例の最短路 $2$ 回の計算で，最大距離のうち最大番号の頂点をとるというようにすればよいです．各頂点 $v$ から長さ $v\cdot \varepsilon$ の長さの辺と葉を追加して直径をとると考えれば正当性が分かりやすいと思います．
これを愚直にやりましょう．毎回中心が消えることから，反復のたびに連結成分の直径は真に小さくなっていきます．このことから，同じ頂点を含む連結成分に対する計算は高々 $O(\sqrt{N})$ 回しか行われないことが分かります．よって適切にこれを実装すれば $O(N\sqrt{N})$ 時間で解けています．
E. Ain and Apple Tree
根から lca までの辺があるたびに +1 すると思って，辺ごとの寄与に分解します．するとスコアは，$\binom{\text{subtree size}}{2}$ の和だと分かります．
スコアの最大はパスグラフの場合で，$\sum_{2\leq i\leq n-1}\binom{n}{i}$ です．これは子が $2$ つ以上ある点があったら適当な葉に付け替えることを考えると示せます．
この最大値以下の $k$ に対して，$k$ または $k-1$ は作れるということが示せます．異なる種類の二項係数を貪欲にとっていくことで，いい感じの subtree size の列がとれます（証明は帰納法）．最終盤で詰まないように許容誤差 $1$ があります．
subtree size の列がとれたら，パスに並べて適当なところに葉を補えば完成です．
F2. Cycling (Hard Version)
やや雰囲気証明気味．
まず prefix について解くというのを無視します．進むために支払うコスト $a_i$ は，広義単調減少としてよいです．増える瞬間があれば直前に使ったやつを距離 $1$ でスワップして再利用することにしても損しないという exchange argument です．
これで，全体を subarray に分割するタイプの問題になります．それぞれについて，初期位置でどこにあった $a_i$ を使うかというのが割り当てられます．
左にある subarray ほど，小さい $i$ に対する $a_i$ を使うこともいえます．冒頭に述べた単調性から，使用順が逆転していたとすると同じものを使用することにしなおす操作ができます．これで，$O(N^3)$ で解けます．
$a_i$ が使われる区間があるならば，それは $i$ を含んでいることもいえます．そうでないとして，境界線の位置をひとつずらすことを考えればよいはず．したがって全区間に対する答を計算するための自然な dp は，$a_i$ による遷移を $L\leq i<R$ の場合の $\dp[L]$ から $\dp[R]$ へと限定することで，Hard 版の「各 prefix に対する答」が自動的に計算できます．
したがって，まず次のような計算手順が考えられます．
- $i=0,1,2,\ldots$ 順に次を行う
- $L\leq i<R$ となる組に対して，$\dp[L]$ から $\dp[R]$ への $a_i$ を使う遷移を行う
コストの計算式を書くと，次のようにできることが分かります：$R$ を無視してまず「一番良い $L$」を見つける．その場合のコストを $R$ に配っていく．
あとはその式を書くと CHT $2$ 個でできることがわかります．$L$ での $1$ 次式を積んでいって，$i$ において最小値をとる．その最小値をもとに $R$ へ配る $1$ 次式を積んでいって，$R$ ではそれを取得．
