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

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

マトロイド

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

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

キーエンス プログラミング コンテスト 2019 E - Connecting Cities (600 点)

めちゃいっぱい解法あってすごい!!!!!!!MST への理解が問われる。 いずれ復習をやり切ってちゃんとしたいが取り急ぎ、分割統治法 Kruskal と、想定解法のみ。 問題へのリンク 問題概要 頂点からなるパスグラフと整数 が与えられる。各頂点には重み が…

AOJ 2224 Save your cat

これ面白いん!!!!!!!!好き!!!!!!! 問題へのリンク 問題概要 平面上に 個の点の座標 と、それらを結ぶ 本の線分がある。 線分のある部分は通過ができないので、線分に囲われた領域とその外側の領域とは行き来することができない。 そこでいく…

Kruskal法をココロから納得する

僕は、最小全域木を求めるKruskal法をココロから納得するのにとても長い時間が掛かってしまいました。本記事では、備忘録的な目的を兼ねて、少しKruskal法について書いてみたいと思います。 僕は、Kruskal法は今年5月頃初めて知ったのですが、そのときはどう…

マトロイドの凸構造

この記事は、Competitive Programming Advent Calendar Div2012の12日目の記事として書きました。 0. はじめに 今回はマトロイドについて書きたいと思います。 マトロイドはGreedyとの関連でよく耳にします。では、そもそもマトロイドがGreedy性を持つのは何…