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
歯医者に行った。
今日のコミット。