2021-05-20 (木)

競プロ

京都大学プログラミングコンテスト2012 - AtCoder: J を解いた。

• J: ネタバレ→最適二分探索木の構築と同様に Knuth-Yao speedup で O(n^2) 時間。←ネタバレ

Indeedなう（オープンコンテスト） - AtCoder: F を解説 AC した。

• F: ネタバレ→愚直はフローに帰着。満点解法はフロー解法に対して結婚定理を適用してそれぞれの好みの人数の条件を得て、4 + 3 で分割して半分全列挙のように分けて計算する。←ネタバレ