Continuation from last time. I solved AtCoder Beginner Contest #130 ~ #133, so I’m summarizing them. I still can’t solve them without explanations…
ABC #130 F - Minimum Bounding Box
Let dp[i][j] be the number of combinations when the i-th and j-th are partial common substrings.
By memoizing the update formula, it can be calculated quickly.
ABC #131 F - Must Be Rectangular!
Consider the (x,y) coordinates as a bipartite graph.
By converting it to a graph, it can be solved smoothly.
ABC #132 F - Small Products
Treat x with the same value of N/x as the same group, and proceed with calculations for each group.
The image is to compress the DP.
ABC #133 F - Colorful Tree
The distance between vertices in a tree structure can be found using LCA (Lowest Common Ancestor). Implementation explanation is summarized in the Ant Book. Read queries in advance and extract necessary vertices and colors. Fill in the necessary values while performing DFS.