E - Sequence Decomposing 問題 数列 が与えられたとき、数列を単調増加となるような部分数列に分けた場合に最小のグループ数を答える問題。 解説 公式解説には「広義の単調減少列の最大の長さ」を求めれば良いとあるが、ここがあまりしっくり来ていない。 …

F - Small Products 問題 正の整数K個を一列に並べたものであって、隣接して並んでいるどの2つの整数の積もN以下であるものの個数を109+7で割った余りを求めてください。 解説 公式解説にあるようにxが最後の整数となるようなi個の整数を並べて条件を満たす…

E - Friendships 問題 N頂点単純連結無向グラフで最短距離が2である頂点対がK個あるものを構築する。 解説 まず最短距離が2である頂点対が最大となるのはある１点（仮に「中心点」と呼ぶ）が他の全ての点と辺を持ち、それ以外の辺が存在しないときである。 …

D - Rain Flows into Dams 反省 二分探索で解けると思ったが、上限下限が決定できるような問題じゃなかった。 解説 に気づけたら実装は簡単。 fn solve(aa: &[i64]) -> Vec<i64> { let s = aa.iter().fold(0, |sum, i| sum + i); let x1 = s - 2 * aa.iter().skip</i64>…

AtCoder Beginner Contest 131 - AtCoder 反省 UnionFind木使うとかどうやったら思いつくんですかね…。 解説 参考: AtCoder ABC 131 F - Must Be Rectangular! (600 点) - けんちょんの競プロ精進記録 fn solve(xys: &[(usize, usize)]) -> usize { let n = …