本当に三分探索で通るのね！ これらの問題を思い出した drken1215.hatenablog.com drken1215.hatenablog.com 問題へのリンク 問題概要 二次元平面上に 本の線分がある。この平面上の円盤 (円周と内部を含む) のうち、 本の線分すべてと共有点をもつようなも…

|x-a| + |x-b| + ... + |x-z| を最小にする x が a, b, ..., z のメディアンになる話は有名で、それを拡張すると仕組みがわかった！ 問題へのリンク editorial 問題概要 体のスライムがいて、それぞれの強さは となっている。以下の操作を行うことができる …

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

今日の ABC 151 F で、「三分探索」とか「山登り法」とか聞いたので！！！ 問題へのリンク 問題概要 二次元平面上に 個の点が与えられる。 今、好きな位置に点を打って、その点から 個の点との距離のうち、大きい順に 個の総和をとる。 上手に点を打ったとき…

幾何だ！！！！！ そして、こういうので「ギリギリを考える」というのは典型な感じ。 なお、僕は最小包含円のことを知らず、アドホックに解いたけど、ライブラリ貼るだけだったらしい... (その方が計算量も少ない) 他にも、三分探索でも解ける！！！ 問題へ…

時刻 に対する面積関数 の最小化問題。 全体で三分探索をするのは嘘。 問題へのリンク 問題概要 二次元平面上に 個の点がある。各点は初期位置から出発して秒速 1 の速度で上下左右のいずれかに動いている。 このとき、 点の の値の最小値を求めよ。 制約 考…

整数の三分探索は闇... 問題へのリンク 問題概要 頂点 辺の無向グラフが与えられる。時刻 0 に頂点 を出発し、頂点 まで移動するのに要する最小時間を求めよ。 各辺にはパラメータ が設定されていて、時刻 にその辺の片側の頂点から出発した場合、もう片側の…