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

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

2020-01-13から1日間の記事一覧

AOJ 3034 Explosion (RUPC 2018 day2-I)

最小包含円シリーズ!!! 問題へのリンク 問題概要 二次元平面上に 個の点がある。これを 個の円ですべて覆うようにしたいです。 これを実現できるような 個の円の半径の最大値として考えられる最小値を求めよ。 制約 考えたこと まず要素技術として、 通り…

yukicoder No.968 引き算をして門松列(その3)

その 2 と雰囲気は似ているけど、一気に考えづらくなった! 問題へのリンク 問題概要 3 つの整数 の組が門松列であるとは、以下の条件を満たすことである。 は互いに相異なる のいずれかが、3 整数の中で 2 番目に大きな値となっている 以下のクエリに 回答…

yukicoder No.967 引き算をして門松列(その2)

ものすごく間違いやすい雰囲気だったので、探索候補を絞ってから力技で全探索した!!! 問題へのリンク 問題概要 3 つの整数 の組が門松列であるとは、以下の条件を満たすことである。 は互いに相異なる のいずれかが、3 整数の中で 2 番目に大きな値となっ…

AOJ 1132 Circle and Points (ICPC 国内予選 2004 D)

最小包含円と似て異なる問題。 問題へのリンク 問題概要 二次元平面上に 個の点がある。 半径 1 の円を上手に配置したときに、その中に含めることにできる点の個数の最大値を求めよ。 制約 考えたこと 「 点のうち 2 点を通る半径 1 の円」に探索候補を絞っ…

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

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

AOJ 2972 All your base are belong to us

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