[自作問題] yukicoder contest 494 オムニバス G - No.3479 Regions by Random Points

最終更新: 2026-05-14

問題概要

正方形内部に $N$ 個のランダムな点を置き、それらすべてを線分で結んだとき、正方形が分割された領域の個数の期待値を求めよ。
・$N \le 10^9$
★3.5

解説

$4 \le N$ の時、 $N$ 個の点と線分の交点の個数を合わせて $V$ とする。$V$ 個の点から $2$ つの点を選び出す方法であって、その二点を通る線が存在するものの数を $E$ とする。また、この線は $2$ 点の間にほかの点が存在し得ない（確率が $0$ ）ので、頂点数 $V$ 辺数 $E$ の平面グラフとなる。すなわち、面の個数はオイラーの定理より $E-V+2$ である。
また、はじめに結んだ $\dbinom{N}{2}$ 個の線分同士の交点の個数を $X$ とすると、 $V=N+X$ 、 $E=\dbinom{N}{2} + 2X$ が成り立つことが分かるので、求める答えは
 $\mathbb{E}\left[\dbinom{N}{2} - N + 2 + X\right] = \dbinom{N}{2} - N + 2 + \mathbb{E}[X]$ であることが分かる。
$N$ 個の点から $4$ 点を取り出すことを考えると、その $4$ 点をそれぞれ線分で結んだ時、交点が $0$ 個または $1$ 個できる。
交点ができる配置(左)とできない配置(右)

交点ができる確率を $P$ とすると、　$\mathbb{E}[X] = \dbinom{N}{4}P$ が得られる。サンプル 1 より、 $P = \dfrac{25}{36}$ が得られるので、答えは $\dbinom{N}{2} - N + 2 + \dbinom{N}{4} \cdot \dfrac{25}{36}$ である。
ただ、これだと面白くないので別の方法で $P=\dfrac{25}{36}$ を示す。
面積が $1$ である正方形の内部でランダムに選んだ $3$ 点がなす三角形の面積を $S$ とする。 $4$ 点のうちから $1$ 点を選び、他の $3$ 点がなす三角形の内部にある確率を考えると、 $P = 1 - 4 \cdot \mathbb{E}[S]$ が分かる。
$\mathbb{E}[S]$ を求める。
点 $P_1 = (x_1, y_1), P_2 = (x_2, y_2), P_3 = (x_3, y_3)$ がなす三角形の面積 $S$ は、
$S = \dfrac{1}{2}\left|\det{\begin{pmatrix}x_2-x_1& x_3-x_1 \\ y_2-y_1 & y_3-y_1\end{pmatrix}}\right|$
$x_1 < x_2 < x_3$ とする。
$\dfrac{1}{2}\left|\det{\begin{pmatrix}x_2-x_1& x_3-x_1 \\ y_2-y_1 & y_3-y_1\end{pmatrix}}\right|\\\,= \dfrac{1}{2} \left| (x_2-x_1)y_3 - (x_2-x_1)y_1 - (x_3-x_1)y_2 + (x_3-x_1)y_1 \right|\\\,=\dfrac{x_3-x_1}{2} \left| y_2 - \dfrac{x_2-x_1}{x_3-x_1}y_3 - \dfrac{x_3-x_2}{x_3-x_1}y_1 \right|$
$\mathbb{E}\left[\left| y_2 - \dfrac{x_2-x_1}{x_3-x_1}y_3 - \dfrac{x_3-x_2}{x_3-x_1}y_1 \right|\right]\\\,=\mathbb{E}\left[\displaystyle\int_{\frac{x_2-x_1}{x_3-x_1}y_3 + \frac{x_3-x_2}{x_3-x_1}y_1}^1\left(y_2-\dfrac{x_2-x_1}{x_3-x_1}y_3 + \dfrac{x_3-x_2}{x_3-x_1}y_1\right)\,\mathrm{d}y_2-\displaystyle\int_0^{\frac{x_2-x_1}{x_3-x_1}y_3 - \frac{x_3-x_2}{x_3-x_1}y_1}\left(y_2-\dfrac{x_2-x_1}{x_3-x_1}y_3 - \dfrac{x_3-x_2}{x_3-x_1}y_1\right)\,\mathrm{d}y_2\right]\\\,=\mathbb{E}\left[\left(\dfrac{x_2-x_1}{x_3-x_1}y_3 + \dfrac{x_3-x_2}{x_3-x_1}y_1\right)^2\right]-\mathbb{E}\left[\dfrac{x_2-x_1}{x_3-x_1}y_3 + \dfrac{x_3-x_2}{x_3-x_1}y_1\right]+\dfrac{1}{12}$
$\mathbb{E}\left[\dfrac{x_2-x_1}{x_3-x_1}y_3 + \dfrac{x_3-x_2}{x_3-x_1}y_1\right]\\\,=\displaystyle\int_0^1\displaystyle\int_{x_1}^1\displaystyle\int_{x_2}^1\displaystyle\int_0^1\displaystyle\int_0^1\left(\dfrac{x_2-x_1}{x_3-x_1}y_3 + \dfrac{x_3-x_2}{x_3-x_1}y_1\right)\,\mathrm{d}y_3\,\mathrm{d}y_1\,\mathrm{d}x_3\,\mathrm{d}x_2\,\mathrm{d}x_1\\\,=\displaystyle\int_0^1\displaystyle\int_{x_1}^1\displaystyle\int_{x_2}^1\left(\dfrac{x_2-x_1}{x_3-x_1}\displaystyle\int_0^1y_3\,\mathrm{d}y_3 +\dfrac{x_3-x_2}{x_3-x_1}\displaystyle\int_0^1y_1\,\mathrm{d}y_1\right)\,\mathrm{d}x_3\,\mathrm{d}x_2\,\mathrm{d}x_1\\\,=\displaystyle\int_0^1\displaystyle\int_{x_1}^1\displaystyle\int_{x_2}^1\dfrac{1}{2}\,\mathrm{d}x_3\,\mathrm{d}x_2\,\mathrm{d}x_1\\\,=\dfrac{1}{12}$
すなわち $\mathbb{E}\left[\dfrac{x_3-x_1}{2}\left| y_2 - \dfrac{x_2-x_1}{x_3-x_1}y_3 - \dfrac{x_3-x_2}{x_3-x_1}y_1 \right|\right]=\mathbb{E}\left[\dfrac{x_3-x_1}{2}\left(\dfrac{x_2-x_1}{x_3-x_1}y_3 + \dfrac{x_3-x_2}{x_3-x_1}y_1\right)^2\right]\\\,=\dfrac{1}{2}\displaystyle\int_0^1\displaystyle\int_{x_1}^1\displaystyle\int_{x_2}^1\displaystyle\int_0^1\displaystyle\int_0^1\dfrac{(x_2-x_1)^2y_3^2 + 2(x_2-x_1)(x_3-x_2)y_3y_1+(x_3-x_2)^2y_1^2}{x_3-x_1}\,\mathrm{d}y_3\,\mathrm{d}y_1\,\mathrm{d}x_3\,\mathrm{d}x_2\,\mathrm{d}x_1\\\,=\dfrac{1}{2}\displaystyle\int_0^1\displaystyle\int_{x_1}^1\displaystyle\int_{x_2}^1\dfrac{\frac{(x_2-x_1)^2}{3} + \frac{(x_2-x_1)(x_3-x_2)}{2}+\frac{(x_3-x_2)^2}{3}}{x_3-x_1}\,\mathrm{d}x_3\,\mathrm{d}x_2\,\mathrm{d}x_1\\\,=\dfrac{1}{2}\displaystyle\int_0^1\displaystyle\int_{x_1}^1\displaystyle\int_{x_1}^{x_2}\dfrac{\frac{(x_2-x_1)^2}{3} + \frac{(x_2-x_1)(x_3-x_2)}{2}+\frac{(x_3-x_2)^2}{3}}{x_3-x_1}\,\mathrm{d}x_2\,\mathrm{d}x_3\,\mathrm{d}x_1\\\,=\dfrac{11}{72}\displaystyle\int_0^1\displaystyle\int_{x_1}^1(x_3-x_1)^2\,\mathrm{d}x_3\,\mathrm{d}x_1\\\,=\dfrac{11}{72}\displaystyle\int_0^1\dfrac{(1-x_1)^3}{3}\,\mathrm{d}x_1\\\,=\dfrac{11}{864}$
$x_1 < x_2 < x_3$ の制約を外すと
$\mathbb{E}[S] = \dfrac{11}{144}$ を得る。
よって、$P = 1 - 4 \cdot \dfrac{11}{144} = \dfrac{25}{36}$ が示された。

実装上の注意

$N=1, 2, 3$ の時は答えがそれぞれ $1, 1, 2$ になる。

AC コード

#include <bits/stdc++.h>
using namespace std;

#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;

int main() {
    mint n; {int x; cin >> x; n = x;}
    if (n == 1 || n == 2) {
        cout << 1 << '\n';
        return 0;
    }
    mint nC2 = n * (n - 1) / 2;
    mint nC4 = n * (n - 1) * (n - 2) * (n - 3) / 24;
    cout << (nC2 - n + 2 + nC4 * 25 / 36).val() << '\n';
}

コメント

コメントを投稿

このブログの人気の投稿

ABC319 G - Counting Shortest Paths

イメージ
作成日: 2026-05-13 最終更新: 2026-05-13 問題へのリンク 問題概要 $N$ 頂点の完全グラフから $M$ 辺を取り除いたとき、頂点 $1$ から頂点 $N$ への最短経路の個数を求めよ。 ・ $2 \le N \le 2 \times 10^5$ ・ $0 \le M \le \min(2 \times 10^5, \binom{N}{2})$ 575 点 解説 全頂点に対して頂点 $1$ からの最短距離が分かれば、距離が小さい順に最短経路の個数を決定できる。 頂点 $1$ からBFS をする。このとき、頂点から出ている辺をすべて見るのではなく、未訪問の頂点のうち、辺が存在するものに遷移すれば $O(N)$ 回の遷移で済む。 頂点 $1$ からの最短距離が分かれば、最短距離で頂点をソートして区間加算・一点取得を高速にできるデータ構造を用いて、最短距離が $k$ の頂点から最短距離が $k+1$ の頂点に遷移することで計算できる。加算をする区間は、取得する位置より後にあるので、いもす法を適用して $O(N+M)$ で計算できる。 全体の計算量は $O(M+ N \log{N})$ 。 サンプル $1$ サンプル $2$ (5/14 追記) ソートはバケットソートを用いることで $O(N)$ でできるため、全体の計算量は $O(N+M)$ にすることができる。 実装上の注意 出力する答えが $0$ の時に $-1$ を出力する実装にしていると、答えが $998244353$ の倍数の時にも $-1$ を出力してしまうので、距離の配列などを使って頂点 $N$ まで到達できるかどうかを判定しておくとよい。 AC コード 提出へのリンク #include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, n) for (ll i=0; i<(ll)(n); i++) const ll mod = 998244353; const int inf = numeric_limits<int>::max()/2; const ll INF = numeric_lim...
続きを読む

ABC320 G - Slot Strategy 2 (Hard)

イメージ
問題へのリンク 問題概要 $N$ 個の長さ $M$ の数字のリールからなるスロットがあり、毎秒一つ以下のリールが止められる。 リールが示す数字をすべて等しくするためには最短何秒かかるか。 ・$N \le 100$ ・$M \le 10^5$ 600点 解説 この問題は、数字ごとに分けて解くことができる。文字種数を $\sigma$ とする。また、解の上界を考えると、示す数字をすべて等しくすることができるならば $NM$ 秒以下でできることが分かる。 これにより、数字 $k$ と正整数 $T (\le NM)$ に対して次のような問題が与えられる（線形計画緩和を用いた）。 $N$ 行 $T$ 列の行列 $v$ が与えられる。ただし、 $$ v_{i,j}= \begin{cases} 1 & (S_{i,j\%M}=k) \\ 0 & (S_{i,j\%M}\neq k) \end{cases} $$ である。 ・$\sum_{i}x_{i, j} \le 1$ ・$\sum_{j}x_{i, j} \le 1$ ・$0 \le x_{i, j}$ これらを満たす $N$ 行 $T$ 列の行列 $x$ に対して、 $\sum_{i}\sum_{j}x_{i, j}v_{i, j}$ を最大化せよ。 この線形計画問題の答えが $N$ ならば $T$ 秒以下で示す数字をすべて $k$ にすることができることが分かる。また、 $T$ に対して答えに単調性があるので、二分探索をすることで解が分かる。 この問題は次のようなグラフを考えることで、最大流問題として解くことができる。 例えば、$N=3, M=3, T=NM=9, v = \begin{pmatrix}0 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 0\end{pmatrix}$ を考える。 v に対応するグラフ このようなグラフから、S からG への最大流を求めることになる。 しかし、これだと頂点数 $O(NM)$ 、辺数 $O(NM)$ になってしまう。頂点数 $V$ 辺数 $E$ の辺容量がすべて $1$ のグラフの最大流はDinic 法を用いることで $O(\sqrt{V}E)$...
続きを読む