前回の続き。Atcoder Beginner Contest #130 ~ #133を解いたので、まとめておく。 まだまだ解説なしでは解けない。。
ABC #130 F - Minimum Bounding Box
dp[i][j]をi,j番目が部分共通文字列となるときの組み合わせ数とする。
更新式もメモ化しておくと高速に計算できる。
ABC #131 F - Must Be Rectangular!
(x,y)座標を2部グラフとみなす。
グラフに置き換えて考えることでスムーズに解ける。
ABC #132 F - Small Products
N/xが同じ値になるxを同じグループとみなして、グループごとに計算を進める。
DPを圧縮していくイメージ。
ABC #133 F - Colorful Tree
木構造の頂点間の距離はLCA（最小共通祖先）を使うことで求めることができる。 実装解説は蟻本にまとまっている。 あらかじめクエリを先読みしておき、必要な頂点と色を抽出しておく。 DFSしつつ必要な値を埋めていく。