A. Alice, Bob, And Two Arrays
大変．
とりあえず文字列長が短ければ $O(NM)$ 時間で解くのは後ろから dp すればよいです．
補助的に「次にこの色を選んだ場合の勝ち・負け」という列を持って，負けの個数を管理したりします．
文字列が連長圧縮形式で入力されます．すると，dp テーブルが，矩形領域に分割されるということになります．大雑把な方針としては，この矩形領域の列を後ろから見て，
– 矩形領域の左上隅の点を始点としたときの結果を求める
– 矩形領域内の始点のクエリに答える
というようなことをやっていきます．前者は何を定義にするかどうかにも選択肢がありますが，「私はその文字を直前のプレイヤがとって，直後にゲームを開始したと仮定した場合」と定義しました．ここは下手だったかもしれません．
dp の値を計算するときには，新しい色をとるタイプの遷移で勝てる場合にはそれでよいのですが，そうでないときに複雑な挙動を計算する必要があります．その領域から新しい色をとって勝てないのであれば，両プレイヤは自色をとる選択肢しかなくて， $(i,j)\to (nxt[i],nxt[j])\to \cdots$ という動きを繰り返します．nxt というのは，ある場所の次の自色です．ある矩形内部では $(i+k,j+k)$ という対角を進むのですが，矩形領域を飛び越えて，同じ色の別の矩形領域に入っていくというかなり厄介なことになります．
色ごとに圧縮した矩形領域での座標を考えて，そこを斜めに進んだときに，はじめて他の色を選ぶことが合理的となる場所は？というクエリを処理することになります．領域を降順に見ながら，$i-j$ がこの区間にあるときにどこまで進むかということを表すデータ構造を持ちます．
色ごとに適当な構造体を持つ感じで実装することになると思います．実装はかなり大変でした．
B. Arithmetic Exercise
どの $x_i$ をプラス，マイナスでとるかを考えると，prefix sum が適切な範囲を保ってプラス，マイナスを選ぶという問題になります．
凸数列の max plus convolution，および，先頭や末尾の削除を行うというタイプの dp 遷移になります．
C. Dreaming Is Not Harmful
はじめに，削除操作を無視した場合の頂点順序を求めておきます．
$v$ に対する答を求めるには，$v$ を含まない部分木を消して，$v$ の手前にある頂点の個数を最小化するという問題を解けばよいです．頂点順序を昇順に処理して，各 $v$ について，部分木 $v$ 内の頂点個数 $cnt[v]$ を持っておきます．クエリでは根から $v$ までのパス以外での $cnt[v]$ の最小値を求めるというようにすればよいです．
D. Cute Subsequences
最大値の和の最大化なので，自由にひとつずつ選んで和の最大化としてよいです．
部分列への分割という部分を処理すると，
- もとの列全体からいくつか選んで得点とする．
- 最後に選んだ要素よりも左にあるもののうち，選ばなかったものの個数分だけ加点．
というような問題になります．最後に選ぶ要素を固定して考えます．「選ばない」をデフォルト状態と考えると，選ぶことに変更する利得が大きい要素を貪欲に指定の個数選ぶというようになります．
