■131:F - Must Be Rectangular!(1937)
X座標、Y座標を二部グラフの問題と解釈し、unionfindで同グループの結ばれていない辺の個数が答え
類題：D - Skate(arc112)
■132:F - Small Products(2143)
状態をまとめて計算量を減らすdp
dp[i][j] := 最後がjで条件を満たす要素数iの数列
これだとO(NK)なのでtle
12の場合
{1}
{2}
{3}
{4}
{5,6}
{7,8,9,10,11,12}のように組分けをする。
{7,8,9,10,11,12}は{1}と
{5,6}は{1}と{2}と
{4}は{1}と{2}と{3}と連結が可能。このようにすると
O(√N * K)に落ちる
■133:F - Colorful Tree (2330)
uとvの距離は
(root,u) + (root,v)-2*(root,lca)で求められる
これをベースに拡張点を訪れたタイミングでその時点で
どの色にどれだけ距離と回数を使っているかを保持しておく
i問個目のクエリの
u,v,lcaのいずれかの箇所に来たらその情報をもとにAns[i]の一部を計算する。
■134:F - Permutation Oddness(2532)
dp[i][j][k]:=i組まで見た、j組がi組内で未マッチング。奇妙さがk
と持つ、答えはdp[N][0][K]
■135:F - Strings of Eternity(2388)
Sを十分な長さだけ連結し、
Tの部分列との一致箇所を探す。
startとendを結び、を繰り返し、roopが作られるならinf
そうじゃないならsize -1 が答え
