最近組み合わせ最適化を勉強中なので、考えたことをメモ 任意の二部グラフ について、次の Kőnig の定理が成り立ちます。 König の定理 の最大マッチングと の最小点被覆は同じサイズを持つ。 この定理の証明はマッチングに関する増加路(augmenting path)を…

今年もICPCに出場したので参加記を書きます。チーム名はCUPC、メンバーは昨年と同じで はにゅ(@hanyu_ipf), stoq(@stoq_), ころも(@uytvcc) の3名です。昨年は惜しくも予選敗退という結果に終わったのと、はにゅさんは今年が最後のため、今年は特に集中しま…

色々雑です 縦線 本から成るあみだくじの上部に と番号を割り振って、それらを辿って下部に番号を書き込んだとします。このときの下部の左から 番目の番号を とします。 このあみだくじが表す置換は ではありません。 が表しているのは 番目に来る数であって…