bobuhiro11's diary

ABC EF問題を埋めた(続き)

15 Jul 2019

前回の続き。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しつつ必要な値を埋めていく。


comments powered by Disqus < ABC EF問題を埋めた ABC135 >