積分
AOJ
JAG
AOJ-ICPC700点
ConvexCut
多角形
面積
ボロノイ図
期待値
積分
分けて解いてまとめる
計算幾何
AOJ-ICPC
JAG春冬コン
図形的量の期待値
競技数学色強め
三角形
浮動小数点型を扱う問題
ボロノイ図の応用問題! 問題へのリンク editorials 問題概要 頂点数 の凸多角形があって、その内部に 個の点が与えられる。凸多角形の内部に一様ランダムに点を打つとき、以下の値の期待値を求めよ。 「その点 から 個の点までの距離の最小値」を二乗した値…
AtCoder
AtCoder600点
ABC-F
ABC-like
積分
橙色diff
テク:K以上からK+1以上を引く
期待値
各区間から1点ずつとってくる問題
区間
連続量問題
座標圧縮
FFT
DP
後ろから解く
差分更新
多項式・FPS(形式的冪級数)
FPS(形式的冪級数)の高等演算
座標圧縮したグリッド上のDP
競技数学色強め
図形的量の期待値
時々やってくる積分ゲー。同時に多項式ゲーでもあった。 問題へのリンク 問題概要 個の区間 が与えられる。これらの区間から一様分布にしたがって点をとってくる (連続値)。 各点の座標の最大値の期待値を をかけた値 (整数値になる) を 1000000007 で割った…
一瞬ヤバそうに見えるけど、落ち着いて考えると、 くらいまで調べればいいという 問題へのリンク 問題概要 正の整数 が与えられるので、 を満たす整数 を一つ求めよ。 制約 考えたこと こういうの、基本的には全探索。でも という制約を見ると、 あたりまで…
AtCoder
AtCoder500点
unrated公式コン
積分
式変形
期待値
Greedy:各要素について独立に考えてよい
競技数学色強め
連続量問題
総和を求める
図形的量の期待値
x軸とy軸について独立に考えてよい
浮動小数点型を扱う問題
積分した 問題へのリンク 問題概要 サイズ の長方形の紙と、それよりサイズの小さいサイズ の長方形の紙が 2 枚あります。 2 枚の小さいサイズの紙を、それぞれ、大きいサイズの紙の中に包含される範囲内でランダムに配置します (その位置は連続量)。 このと…