Greedyなマッチング
Greedy を考察して、さらに左右から累積和を求める！結構難しい！ 問題へのリンク editorial 問題概要 長さ の数列 と、長さ の数列 が与えられます。各 に対して、次の値を求めよ。 数列 から を除去してできる長さ の数列 を考えて、数列 を適切に並び替え…
最小包含円と、マッチングの二部構成問題 問題へのリンク 問題概要 個の円 ( と番号付けされている) と、 個の多角形 ( と番号付けされている) とが与えられる。 各円は、中心の座標と半径 各多角形は、各頂点の座標 が与えられる。すべての多角形が、いずれ…
最高に好きな問題 問題へのリンク 問題概要 頂点数 のツリー上でゲームを行う。高橋君は残った頂点から 1 つ選んで白く塗る。青木君は残った頂点から 1 つ選んで黒く塗る。 この操作をすべての頂点に色が塗られるまで繰り返したとき、黒く塗られたすべての頂…
楽しかった。7 時間かかったけど自力 AC できたー！ 問題へのリンク 問題概要 正の整数 が与えられる。 個の 以上 未満の整数 を 個ずつのペアに分けたい。 各ペア に対して % の値 (これを醜さと呼ぶ) を求め、その最大値をとる。 この最大値の最小値を求め…
こどふぉらしい問題という感じかな。脈略のないような対象が継接ぎされた感じの問題 ^^; 問題へのリンク 問題概要 長さ の整合のとれたカッコ列全部を集めた集合についての trie 木を作る。 この trie 木上の最大マッチングのサイズを 1000000007 で割ったあ…
いい感じの Greedy 問題 問題へのリンク 問題概要 個の文字列 が与えられる。2 つの文字列 について、 の最後 i 文字と、 の最後 i 文字が共通 の後ろから i 文字目も、 の後ろから i 文字目も c である という条件を満たすとき、ラベル (i, c) をつけながら…
こういう貪欲は確実に抑えて行きたい 問題へのリンク 問題概要 長さが の線分がそれぞれ 本ずつある。 これらから三角形は最大で何個作れるか？ 制約 考えたこと 面白そう！！！！！ な量を扱う問題リストにまた 1 問加えられる！！！！！ この手の問題では…
難しくて、てんぷらたんが天才だった！！！！！！！ とにかくすごかった！！！！！ そしてすごく面白い問題だった！！！！！ 問題へのリンク 問題概要 長さ の数列 が与えられる。数列の 2 要素を選んで swap する操作を高々 回まで行うことができる。 操作…
Greedy を信じよう...じゃなくて、証明しよう！ 問題へのリンク 問題概要 枚の絵画があって、それぞれ大きさは 、価値は で与えられる。 個の額があって、それぞれ大きさが で与えられる。 絵画と額とをマッチングさせる。ここで、以下の条件を満たすような…
「交換しても悪化しない」というのは Greedy の証明の共通構造だとは思う。 問題へのリンク 問題概要 個の正の整数 がある。 これらの 個の整数に対応する 頂点のグラフを考えて、和が の形で表せる 2 数間に辺を引く。 このグラフの最大マッチングを求めよ…
