最近フロー関連をやってたのでそのメモ 最大流 頂点辺の有向グラフ 各辺には容量が定義されている をそれぞれ頂点から出る/入る辺の集合とする 始点を，終点をとする LPの形で書くと以下の通り ford-fulkerson 最大流を求めるアルゴリズムの一つ 最大流の流…

燃やす埋める問題は以下の問題である 頂点を赤と青に塗り分ける 塗り方の依存関係によってスコアが変動する (例) 頂点 が赤で頂点 が青に割り当てられたとき 失う スコアの和の最小化を行え この問題は最小カットに帰着して解くことができる 必ず赤が割り当…

問題ページ 基本的に使用している文字は公式解説と同じ意味になるように使っています． 回操作ができるような整数のうち最大のものをとする． を数列に含まれるの個数とする．回操作するとき，整数を選択できる回数は 回である．よって回操作をするときに，…

数え上げにおいてときどき現れる．括弧列の数・多角形の分割・グリッドの経路数などがカタラン数で表される． 参考資料 wikipedia 括弧列・二分木・最短経路・三角形分割・平面グラフ・非交差分割 高校数学の美しい物語 トーナメント・最短経路・三角形分割 …