CF後twitterで話してたのでまとめた。 楽しかった。togetter.com3*Nに対するエレガントな解答を募集しています。

雑な記事。 競プロテクをtweetしただけだといつか流れてどっか行くので、とりあえずまとめといた。togetter.com

前編はこちら前編は汎用性も高い話題でしたが、後半は少しマニアックで雑学的です。 予習 全方位木DPについて予習します。全方位木DP、有向辺に関するDPだと思うのが分かりやすい。1. 青い矢印は普通の木DPで下から順に求まる2. 根から出る矢印は全部求まっ…

この記事はCompetitive Programming Advent Calendar 2018の46日目の記事として書かれました（嘘）最近、木上のアルゴリズムの面白い計算量解析が２つ話題になったのでまとめておきます。 予備知識 まず、https://web.archive.org/web/20150819082918/https:…

ARC092C - 2D Plane 2N Pointsの証明が話題になってたっぽいので問題を見てみたら、最大マッチング系貪欲の証明テクが詰まった問題だなぁと思ったので書いてみた。 問題概要 平面上に赤い点と青い点がある。 赤い点が青い点の左下である（つまりxもyも小さい…