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

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

連続量問題

CodeQUEEN 2023 決勝 F - Queen's Crown

AOJ 2373 HullMarathon とよく似た問題。 問題へのリンク 問題概要 二次元平面上に 点を以下の条件を満たすように配置する。各点を とし、偏角を とする。 点 と、原点との距離は このとき、多角形 の面積の最大値を求めよ。 制約 考えたこと ほとんどこの問…

AOJ 2373 HullMarathon (JAG 冬合宿 2010 day3-E) (700 点)

面白い最適化問題! 問題へのリンク 問題概要 二次元平面上で、原点からの距離が であるような 点の凸包の面積として考えられる最大値を求めよ。 制約 考えたこと 凸包というところが面倒だが、要は 本のうちの何本かを選んで それを適切な順序に並び替えた…

AtCoder ABC 314 Ex - Disk and Segments (赤色, 625 点)

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

AtCoder ABC 207 D - Congruence Points (黄色, 400 点)

すごくシンプルだけど詰まる部分もたくさんありそうな問題 問題へのリンク 問題概要 二次元平面上に、2 組の 個の点集合 、 がある。 に含まれる 個の点に対して、一律に 原点を中心とした回転をする (角度は任意) 平行移動をする (移動量は任意) を実施する…

AOJ 2345 Network Reliability (JAG 冬コン 2011 F) (700 点)

ABC 213 G の類題に挙がっていたのでやってみた! 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられます。また 以上 以下の整数 が与えられます。 グラフの各辺は % の確率でそれぞれ独立に消失します。グラフ全体が連結である確率を求め…

square869120Contest #5 B - Emblem

競プロ典型90問の問題 001 の類題。「最大値の最小化」をする二分探索の典型問題ですね。 問題へのリンク 問題概要 二次元平面上に 個の円が与えられます。またそれらとは別に 個の点が与えられます。円同士は互いに交わることはなく、点が円に包含されるこ…

AtCoder ABC 026 D - 高橋君ボール1号 (試験管水色)

方程式を解くタイプの二分探索の問題ですね。 問題へのリンク 問題概要 正の整数 が与えられます。 秒後のボールの位置 は で表されます。 を満たす実数 の値を十分高い精度で求めてください。 を満たせば正解とみなされます。 制約 解へのアプローチ の解を…

AtCoder AGC 039 D - Incenters (赤色, 1000 点)

銅色 diff 問題が自力で解けて嬉しい。(修正:赤色になった) 問題へのリンク editorial 問題概要 原点を中心とする半径 1 の円周上に 個の点 がある (偏角が入力として与えられる)。 これらの点からランダムに 3 点選んでできる三角形の内心の座標の期待値を…

AOJ 2629 Manhattan (JAG 夏合宿 2014 day2-A) (250 点)

伝説のりんごさんセットの 1 問目 問題へのリンク 問題概要 二次元座標平面上において、 座標と 座標のうちの少なくとも一方が整数であるような点からなる集合を「道路」と呼ぶ。 道路上の 2 点 のユークリッド距離が実数 で与えられる。 点 から道路のみを…

HHKB プログラミングコンテスト 2020 F - Random Max (橙色, 600 点)

時々やってくる積分ゲー。同時に多項式ゲーでもあった。 問題へのリンク 問題概要 個の区間 が与えられる。これらの区間から一様分布にしたがって点をとってくる (連続値)。 各点の座標の最大値の期待値を をかけた値 (整数値になる) を 1000000007 で割った…

AOJ 3034 Explosion (RUPC 2018 day2-I)

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

AOJ 2972 All your base are belong to us (JAG 夏合宿 2019 day1-F)

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

AtCoder ABC 151 F - Enclose All (青色, 600 点)

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

Codeforces 551 DIV2 F - Serval and Bonus Problem (R2800)

こういうのに慣れて行きたい。 問題へのリンク 問題概要 長さ の線分上に、ランダムな区間を 個とったときの、区間が 本以上重なっている部分の長さの期待値を求めよ (998244353 で割った余りの形式で)。 なお、区間のランダムな選び方とは、線分から 2 点ず…

AOJ 3054 Tunnel (RUPC 2019 day2-D)

離散量だなんて思わなかった。。。 問題へのリンク 問題概要 (略) 個の長方形からなるヒストグラム (x 座標が から の範囲に存在していて、それぞれの長方形の高さが ) が与えられて、それに合わせて折れ線を最適化する。 折れ線の始点は 正の整数 があって…

みんなのプロコン 2019 決勝 A - Affiches (500 点)

積分した 問題へのリンク 問題概要 サイズ の長方形の紙と、それよりサイズの小さいサイズ の長方形の紙が 2 枚あります。 2 枚の小さいサイズの紙を、それぞれ、大きいサイズの紙の中に包含される範囲内でランダムに配置します (その位置は連続量)。 このと…

AOJ 1157 大玉転がし (ICPC 国内予選 2008 E) (450 点)

ごろごろごろごろ 問題へのリンク 問題概要 球を、地面を点 から点 へと直線的に移動する。 直線の周りには直方体が配置されていて、その直方体と球が物理的に干渉しないようにしたい。 極端な話、球の半径が ならば干渉することはない。球の半径をどこまで…

AOJ 3044 Timing (AUPC 2018 day3 F)

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