Just a moment...
codeforces.com
A. Diagonal Walking
手前から見て可能なら置き換える貪欲．
B. String Typing
at most once なので，どの長さのときに倍化するかを決めて計算するだけです．
C. Matrix Walk
$1$ でない差があればそれが縦幅です．候補が 1 通りに絞れたらチェックします．
D. Fight Against Traffic
$s,t$ から各点への距離を前計算．$\binom{n}{2}$ 通りすべてを試せます．
E. Water Taps
$t-T$ の総和が $0$ になるように貪欲にとります．総和が正だとすると負のものは全部使って，正のものは $0$ に近いものから優先的に使います．
F. Runner’s Problem
$3$ 状態の dp ができて，これは $(3,3)$ 行列の積として表現できます．区間ごとに行列があってその総積を求めるという問題に帰着できます．
G. Castle Defense
二分探索します．判定問題では場所ごとに必要回数が決まっていて，必要回数以上ずつを被覆するように固定幅の区間を置いていくというものです．足りない部分が出てきたときにそれを左端とする区間を必要個数置くという貪欲法でよいです．被覆回数を求める累積和のテクニックが判定問題でも使えて判定問題は線形時間でできます．
H. Path Counting
深さ $d$ の点に対して，それを端点として子方向にのびるパスの母関数 $f$ を持ちます．$g(x) = 1+nxf(x)$ f$ のような更新をすることになります．
各点を lca とする場合の答の計算では $f^2$ が必要になります．組 $(f,f^2)$ を持つようにすると線形時間で更新できます．
I. Yet Another String Matching Problem
計算量を無視すれば，コストの計算は，a から f の 6 頂点のグラフの $s[i],t[i]$ 間に辺を結んだときの連結成分です．これを $N-M+1$ 個の区間で並列に計算します．$2$ 頂点を決めたときに辺があるかどうかは畳み込みで計算できます．
