srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

二部マッチング

codeforces 401 div2 B. Game of Credit Cards

問題 問題概要 数列a, bが与えられる. 数列bは好きな順番に変更することができる. (1) a[i] > b[i] となる i の個数の最小数 (2) a[i] < b[i]となる i の個数の最大数 を求める問題 解法 2部マッチングの最大数を使ってとく. 数列bを任意の順番に動かすこと…

天下一プログラマーコンテスト2015予選A C - 天下一美術館

問題 問題概要 マスの状態を一致させるために、必要な最小コストを求める問題。 解法 はじめは、貪欲に、左上から見ていき、交換して変えて、一致するところを優先的にやればいけると思い書いたが、WA。原因は単純で、左上から貪欲にやるだけではだめで、ど…

aoj 2480 - Blame Game

問題 問題概要 Aliceから順に相手の欠点を選ぶ。次にボブは選ばれた欠点と関係あるAliceの欠点を選ぶ。これを続けていき、選べなくなったら負け。 解法 2部マッチングかなて感じはするが、どちらが勝つのかという判定をどうすればいいかわからなかった。 感…

aoj 1163 - Cards

問題 問題概要 青と赤のカードがある。青と赤のカードを選び、その2つの数が1より大きい約数を持つなら取ることができる。一度取った数字は次から選ぶことができない。何組のカードが取れるか。 解法 ペアの個数はペアを作る組によって変わってくる。約数を…

yukicoder No.421 しろくろチョコレート

問題 問題概要 省略 解法 2部マッチングでできるのか、て感じ。公式解説を見ればわかる。実装はs,tを追加して、最大フローを求める感じで書いたもの。 ミス 制約が小さければ、bitDPでもできるぽい。グラフ問題に落とせるようにしたい。 コード #include <iostream> #i</iostream>…

aoj GRL_7 A Matching - Bipartite Matching

問題 問題概要 省略 解法 2部マッチングの確認問題 ミス 蟻本のやつを写経した。 コード #include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) const int INF = 1e9; co</algorithm></cstring></vector></cstdio></iostream>…