A. New Year String
それぞれの目的に必要なコストを計算します．
前者は連続 $4$ 文字を全探索でよいです．後者はこの場合 $2025$ 同士は重複しないので，$2025$ の個数を数えればよいです．
B. New Year Cake
何段積み上げるかを探索すればよいです．$20$ 段ちょっとという範囲しか調べないでよいです．
C. Production of Snowmen
- $a$ をいくつずらすか
- $b$ を $a$ と比べていくつずらすか
- $c$ を $b$ と比べていくつずらすか
という独立な選択に分解できます．最初のものは $N$ 通り，他のものは $N$ 通りのうち条件を満たす方法を全探索で調べます．
D. Christmas Tree Decoration
$a_i$ の sum を $S=nq+r$ として，$n-r$ 個の箱には $q$ 回，$r$ 個の箱には $q+1$ 回操作が来ます．
$q+2$ 個以上の箱が番号 $1$ 以上にあると詰み．そうでないとき，ちょうど $q+1$ 個の箱について「順列の先頭 $r$ 個のどれかです」という条件がつきます．
E. New Year’s Gifts
まず $y_i$ ずつ払っておきます．アイテムは組 $(x,z-y)$ として扱えます．
最も小さい箱について，入れられるアイテムがなければ当然捨ててよいです．
入れられるアイテムがあれば，どれかは入れるとしてよいです．さらにそのうちで $z-y$ が最大のものを入れるとしてよいです．これらは簡単な貪欲です．
これで箱をすべて処理し終わったら，単に 「$z-y$ を支払うことで $1$ 点を得られるアイテム」がたくさんあるだけになって，これも安いものから貪欲にとっていけばよいです．
F2. Christmas Reindeer (hard version)
$c$ と $c’$ がかなり紛らわしいので，$a_i=2^{c_i}$ などと書きます．
まず capacity は $\sum \frac{a_k}{2^k}$ としてよいです．floor による切り捨ての総和の影響は $1$ 未満になるからです．この値を $f(a)$ と書きます．
次に，$a_k$ が降順な $2$ べきの列という条件下，では，$f(a), f(b)$ の比較が $a,b$ の辞書比較と一致するというのが重要ポイントです．これはある項ではじめて差がつくとそれ以降では挽回不可能だからです．
よってまず，$f(a)=x$ となる列 $a$ を作ります．これは貪欲な $2$ べきを採用していけばよいです．
これができたら，辞書順で $a$ 以上であるような列を数えればよいです．降順ソート列の辞書順なので，大きな $c_i$ から順に頻度を数えた頻度列の辞書順ということになります．
lcp ごとに数えることを考えれば，数えられます．
計算量削減要素としては，「$k$ の出現頻度ではじめて $a$ を上回る」というタイプの計算をしようとすると $\sum_{i=l}^n\binom{n}{i}$ のような和が登場します．これは全体から引くという形で処理すれば $O(l)$ 時間です．
結局，変更クエリでは各値の頻度だけ保持するようにすれば，何もかもが $O(max c_i)$ 時間で計算できます．
G. Short Garland
条件は単に，何らかの DFS 順にとっていくというものです．
木 DP を考えて，部分木ごとの答を求めていきます．「答」としては，最後の頂点の深さごとの数え上げを持ちます．
subtree をマージするときには，どの subtree を最後にするかが重要になります．その他の subtree は深さ $dep[v]+K-1$ 以下であるような頂点が最後の頂点にできます．
あとはこれを適切に高速化すればよいです．例えば DSU on Tree のようなことを考えて，heavy child の答を保持しながら light child たちの結果を追加するという形にします．すると遅延セグメント木を（問題を通して）ひとつ持てば実装できます．$O(N\log^2N)$ 時間．
そういえばこれは，depth が等しい点がマージされていく木 DP なので，heavy light decomposition よりも長鎖分解？longest path decomposition？（用語があやふや，最大深さの子を heavy child と思う）ことで高速になったりしたかも．
あとは「深さ $dep[v]+K-1$ 以下であるような頂点」に対する総和クエリが必要であるため私はこれを遅延セグメント木の区間クエリで処理したのですが，深い方から順に要らなくなっていくだけなので，配列を使ってみる範囲をスライドしていくだけでも上手くいったりするかもしれません．
再考して，$O(N\log MOD)$ になるというのが面白い問題ということだと思います．
次のマージテクの亜種があります：長さ $n,m$ の $2$ つの dp テーブルを $O(\min(n,m))$ 時間でマージして，$\max(n,m)$ の長さの dp テーブルにする．これはデータの移動 $O(N)$ 回です．
今回は dp[v からの距離] という形の dp テーブルを考えるとやりたい操作は
- 先頭に 0 を挿入
- 2 つの列をマージ： $\dp[i]:=c_1 \times \dp_1[i] + c_2 \times \dp_2[i]$ の要領．
- prefix sum の取得，ただし和をとる範囲はスライド
という形なのでできます．「列全体を定数倍する」「値を加算する」というところで $0$ 倍が入ると困りますが，$0$ 倍が来たらすべて破棄したりすれば大丈夫でしょう．ただし，定数倍してから加算するという操作において逆元が欲しくなって $\log MOD$ ということになる気がします．
