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

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

二部グラフ

Codeforces Round #682 (Div. 2) C. Engineer Artem (R2000)

グリッドグラフは二部グラフ!!! 問題へのリンク 問題概要 のマス目に整数値 (マス には ) が書かれている。 各マスについて、「元の整数値のままにする」または「元の整数値に 1 を足したもの」をすることによって、どの隣接する 2 マスの値も互いに相異…

Codeforces Round #680 (Div. 1) C. Team-Building (R2500)

undo 付き Union-Find ってなんぞ!? 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。色が 種類あって、各頂点は のいずれかの色で塗られている。このとき、以下の条件を満たすような色の組 () の個数を求めよ。 個の頂点のうち、色…

AOJ 2679 Decoding Ancient Messages (JAG 春コン 2014 C) (700 点)

多倍長整数を活用した、重み付き二部マッチング 問題へのリンク editorial 問題概要 のグリッドが与えられる。各マスにはアルファベット (英大文字と英小文字) が描かれている。今、次の条件を満たすように 個の文字を抜き出す 各行から選ぶマスはちょうど 1…

Codeforces Grakn Forces 2020 E. Avoid Rainbow Cycles (R2400)

むずかしい 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。これらはある操作のコストを決めるためのパラメータである。 さらに、 系列の数列が与えられる。 番目の数列の項数は で与えられる 数列の各項 は 以上 以下の値である 今、…

AOJ 3168 Capture Ebichan (HUPC 2020 day1-E)

アルファベットは 26 文字!26 は偶数! 問題へのリンク 問題概要 (意訳) 頂点数 、辺数 の無向単純グラフ が与えられる。各頂点 には、1 文字の英小文字 が振られている。ここで正の整数 が与えられ、改めて次のように定義されるグラフ を考える の頂点集合…

Codeforces Round #626 (Div. 1) C. Instant Noodles (R2300)

割と TLE に関して危険な橋をわたっていたのかもしれない。でも、ロリハとかしなくても大丈夫だった。 問題へのリンク 問題概要 左頂点数と右頂点数がともに であるような二部グラフが与えられる。二部グラフの辺数は である。 右頂点 には値 がある。今、左…

AOJ 2581 完全順列 / Derangement (RUPC 2014 day3-G)

今の RUPC / AUPC の先駆けとなった合宿の北大セットの問題!!! このセットは、全問題のタイトルの頭文字が 'D' というセットだった セットへのリンク 北大アーカイブへのリンク 問題へのリンク 問題概要 長さ の順列 が与えらえる。これらを並び替えて完…

Codeforces Round #616 (Div. 1) C. Prefix Enlightenment (R2400)

Union-Find を使いこなす!!! 問題へのリンク 問題概要 (意訳) 個の 0-1 変数 が与えられていて、最初はそれらの値について特に制約はない。いま、 個の制約が順に与えられる。各制約はそれぞれ 1 つの変数 と 0 か 1 の値 w を指定して、 とする 2 つの変…

CODE FESTIVAL 2016 qual A D - マス目と整数 / Grid and Integers (橙色, 800 点)

800 点埋めをしていく!!! 問題見て、コーナーケース怖い系かな...と思ったけど、ちゃんと一発で通せてよかった 問題へのリンク 問題概要 行 列のマス目があって、以下の条件を満たすように各マスに整数値を書き込みたい (整数値を とする): どのマスの数…

キーエンス プログラミング コンテスト 2020 E - Bichromization (黄色, 900 点)

実装に精彩を欠いてしまった...コンテスト中に WA を取りきれず... WA の原因は「すでに色を決めたはずの頂点について再度色を上書きしていることがある (現在見ている D 値について、それより小さい値の頂点とはつながっておらず、等しい D 値同士で結ばれ…

Educational Codeforces Round 80 F. Red-Blue Graph (R2900)

需要供給を考え、さらに最小流量制約もある最小費用フロー!!! 問題へのリンク 問題概要 左頂点数 、右頂点数 、辺数 の二部グラフが与えられる。各頂点は「赤」または「青」または「白」に塗られている。 さて、各辺は最初は白色である。そのうちの何本か…

AOJ 2423 コードアートオンライン / Code Art Online

最小包含円と、マッチングの二部構成問題 問題へのリンク 問題概要 個の円 ( と番号付けされている) と、 個の多角形 ( と番号付けされている) とが与えられる。 各円は、中心の座標と半径 各多角形は、各頂点の座標 が与えられる。すべての多角形が、いずれ…

第一回日本最強プログラマー学生選手権-予選- D - Classified (青色, 600 点)

初見時は証明なしに再帰的にやった... 問題へのリンク 問題概要 頂点の完全グラフがあたえられる。 このグラフの辺に、非負整数値を付けていく方法のうち 整数値が等しい辺のみからなる部分グラフが奇数長のサイクルを含まない という条件を満たす範囲内で、…

第一回日本最強プログラマー学生選手権-予選- E - Card Collector (橙色, 800 点)

マトロイドだ!!!!!!! 問題へのリンク 問題概要 のボード上の 個のコマがあってそれぞれ重みがつけられている。同じマスに複数のコマが置かれていることもある。 今、各行から 1 個以下のコマを取り去る。次に各列から 1 個以下のコマを取り去る。 最…

Codeforces Round #586 (Div. 1 + Div. 2) D. Alex and Julian (R1900)

すごく面白かった 問題へのリンク 問題概要 (表現改) 個の正の整数 が与えられる。これらから最小個数を取り除いて、以下の条件を満たすようにせよ。 残った整数から重複を許して奇数個選ぶどのような方法に対しても、選ばれた整数を 2 つに分けてそれぞれの…

Codeforces 500 DIV1 B. Chemical table (R1900)

確かに、ついこの間の ABC 131 F の類題だね 問題へのリンク 問題概要 のグリッドがあって、 マス分が黒く塗られている 長方形の三頂点状に並んだ黒マスの組を選んで、残りの頂点に相当する位置を黒く塗る (コスト 0) 黒くないマスを一つ選んで黒く塗る (コ…

AtCoder ABC 131 F - Must Be Rectangular! (青色, 600 点)

なんか既視感があった。それがどこから来たのか、いまだよくわからない。。。 問題へのリンク あと、今回のような二部グラフの作り方はあり本 P.205 の POJ 3041 Asteroids あたりもそんな感じ。こういうのを一度見ておくと、この二部グラフ作りは定石になる…

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

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

AtCoder ABC 126 D - Even Relation (水色, 400 点)

とても教育的なツリーの探索問題。 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。このグラフの各頂点を白黒に塗る方法であって 同色に塗られた 2 頂点はどれを選んでも、その間のパスの長さは偶数である という条件を満たすものを求めよ…

AtCoder AGC 032 D - Rotation Sort (橙色, 1000 点)

本番フローで無理矢理解いた!!! でも DP が本筋だね。 問題へのリンク 問題概要 の順列 が与えらえる。これを 整数 を選んで区間 [ ) を左シフトする、すなわち をそれぞれ へ置き換える、これにコスト がかかる 整数 を選んで区間 [ ) を右シフトする、…

AOJ 2943 イルミネーション (RUPC 2019 day1-G)

燃やす埋めるは今度こそちゃんとマスターする!!! 問題へのリンク 問題概要 × の各格子点に電球がある。 が偶数となるような について、 を頂点とする正方形の中心に装置があって、各装置を押すことで四隅の電球を点灯することができる。 ただし、装置を起…

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

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

AOJ 2370 RabbitWalking (JAG 冬合宿 2010 day3-B) (600 点)

これを解いていたおかげで ARC 099 E - Independence がすぐに思いつけた感はあるかも。むしろ制約的に ARC 099 E の完全上位互換だと言える。 問題へのリンク 問題概要 頂点 辺の無向単純グラフが与えられる。 このグラフが「奇数長のサイクルがない」とい…

AtCoder AGC 003 D - Anticube (橙色, 1100 点)

とくらちゃん・シンヤカトー・てんぷらたんたちと気合いで解いた。 問題へのリンク 問題概要 個の正の整数 が与えられる。この中から最大個数の要素を取り出して どの 2 つをとってもその積が立方数とはならない という条件を満たすようにせよ。 制約 解法 …

Codeforces Round #511 (Div. 1) B. Little C Loves 3 II (R2200)

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

POJ 3692 Kindergarten (ARC 099 E の類題として)

ARC 099 E - Independence の類題という感じなん。具体的には「補グラフをとって二部グラフを考えて...」みたいなところのが似てるん。 POJ 3692 Kindergarten 問題概要 G 人の女の子と、B 人の男の子がいて、「女の子同士」「男の子同士」はすべて互いに知…

AtCoder ARC 099 E - Independence (黄色, 700 点)

いわゆる本当に典型らしい典型ではあるけれども、「二部グラフ判定」と「ナップサック DP」とパートが 2 つあって重たいのん。こういうのを素早く通せるようになりたいん。 類題として AOJ 2370 RabbitWalking (二部グラフ判定からの部分和ナップサックが酷…

AtCoder AGC 025 D - Choosing Points (赤色, 800 点)

二部グラフ解法頭いいと思ったものの、整数論的考察で通したのでその報告を。TL 見た限りだと、kirika さんと同じ解法っぽいですがかなり少数派っぽいです (ただし、自分はイデアルという概念を意識できてはいなかったです...)。 d1=2^k * u (u は奇数) とす…

Codeforces Round #360 (Div. 1) A. NP-Hard Problem (R1500)

http://codeforces.com/contest/687/problem/A リハビリ第一弾 問題概要 無向グラフ (頂点数 n, 枝数 m) が与えられる。 このグラフの頂点集合を互いに disjoint な 2 つの集合 A, B に分割して、 A, B がともに vertex cover となっているようにせよ。 その…