けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

二部マッチング

SoundHound 2018 予選 C - 広告 (400 点)

ちょっと話題になった超典型フロー 問題へのリンク 問題概要 のグリッドがあります。各マスは白黒に塗られています。今、白いマスにできるだけ多くのコマを置きたいです。 各マスに 1 個のみ コマを置けるのは白いマスのみ 隣り合う白マスの双方にコマを置く…

AOJ 1163 カードゲーム (ICPC 国内予選 2009 E)

高速な二部マッチング、Hopcroft-Karp 法を整備した 問題へのリンク 問題概要 N 枚の赤いカードと、M 枚の青いカードとの間で最大マッチングを作りたい。 各カードには整数値が書かれていて、最大公約数が 1 より大きいカード同士をペアにすることができる。…

Codeforces 511 DIV1 B - Little C Loves 3 II

なんとか解けてよかった 問題へのリンク 問題概要 × の二次元グリッド盤面が与えられる。 空いているマスを 2 つ選んで、その 2 つに駒を置く。ただしその 2 マス間のマンハッタン距離が 3 でなければならない という操作を繰り返し行う。こうして出来上がる…