drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder600点 ABC-G 橙色diff 構築 Yes/No判定問題 復元 フロー グラフ 【問題集】フローのステップアップ 順列を題材とした問題 解空間:O(N!)通りの選択肢 順列の最適化問題 マッチング 二部マッチング Hallの結婚定理 操作 操作:permute 数学的帰納法に基づく考察 彩色問題 二部グラフ 二次元グリッド NoviSteps4D 面白かった 問題へのリンク 問題概要 のグリッドがある。各マスには数値が書かれている。 個の数値を集めると、 が 個ずつある。 今、各行について、その 個の数値を自由に並び替えていく。 その結果として、すべての列が の順列であるようにすることが可能かどうかを判定し、可能ならば操作後のグリッドを出力せよ。 制約 解法 結論から言えば、 回、二部マッチング問題を解けばよい。 まず補題として、どんなグリッドにおいても、左端を の順列にすることが可能であることに注意する (Hall の定理から従う)。 そうすると残りは のグリッドの問題になるが、帰納法的に左端を の順列にすることが可能である。 たとえ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2023%2F08%2F27%2F000216" title="AtCoder ABC 317 G - Rearranging (4D, 橙色, 600 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1687765056723440 Hatena Blog https://hatena.blog 2023-08-27 00:02:16 rich https://drken1215.hatenablog.com/entry/2023/08/27/000216 1.0 100%