blog.bouzuya.net

2022-01-22 第八回 アルゴリズム実技検定 (PAST) K - ニワトリのお見合い を解いた

第八回 アルゴリズム実技検定 (PAST) K - ニワトリのお見合い を解いた。

問題: https://atcoder.jp/contests/past202109-open/tasks/past202109_k

全探索はできそうにない。S の各行からうまくひとつずつを選ぶ……とか……? DP ? 過去に選んだものを保持するのが厳しそうだ……。そんなことを考えたものの諦めて解説を読んだ。

解説: https://atcoder.jp/contests/past202109-open/editorial/2727

重み最大化二部マッチングの問題。ネットワークフロー。本では何度か見ているんだけど解ける気がしない。 2 の最小費用流に帰着して解く方法で解いた。

https://qiita.com/drken/items/e805e3f514acceb87602 も合わせて読んだけど。まだ解ける感じがしない。

提出: https://atcoder.jp/contests/past202109-open/submissions/28670632


歯医者に行った。


今日のコミット。