問題一覧 > 通常問題

No.2873 Kendall's Tau

レベル : / 実行時間制限 : 1ケース 4.500秒 / メモリ制限 : 512 MB / 小数誤差許容問題　絶対誤差または相対誤差が$10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 78
作問者 : 寝癖寝癖 / テスター : yuusaanyuusaan 👑 seekworserseekworser
1 ProblemId : 11163 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-07-17 23:44:48

問題文

$N$ 個のデータ $(x_1,y_1),\cdots,(x_N,y_N)$ が与えられるので、ケンドールの順位相関係数を求めてください。

ただし、ケンドールの順位相関係数 $\tau$ は以下のように定義されます。 \[\tau=\frac{P-Q}{\sqrt{R\times S}}\]

  • $P$: 異なる添字の組 $(i, j)\ (1\le i < j\le N)$ であって、$(x_i-x_j)(y_i-y_j)> 0$ となるようなものの個数
  • $Q$: 異なる添字の組 $(i, j)\ (1\le i < j\le N)$ であって、$(x_i-x_j)(y_i-y_j)< 0$ となるようなものの個数
  • $R$: 異なる添字の組 $(i, j)\ (1\le i < j\le N)$ であって、$x_i\neq x_j$ となるようなものの個数
  • $S$: 異なる添字の組 $(i, j)\ (1\le i < j\le N)$ であって、$y_i\neq y_j$ となるようなものの個数

なお、本問題の制約上、$R\times S\neq0$ となることが保証されます。

入力

$N$
$x_1\ y_1$
$\vdots$
$x_N\ y_N$
  • $2\le N\le 2\times10^5$
  • すべての $i$ に対して $|x_i|,|y_i|\le10^9$
  • 異なる添字の組 $(i,j)$ が存在して $x_i\neq x_j$
  • 異なる添字の組 $(i,j)$ が存在して $y_i\neq y_j$
  • 入力はすべて整数

出力

ケンドールの順位相関係数を一行で出力してください。

なお、想定解答との絶対誤差または相対誤差が $10^{-6}$ 以下であれば正解と判定されます。

サンプル

サンプル1
入力
3
1 4
1 5
9 2
出力
-0.8164965809277260

ケンドールの順位相関係数の定義における $P,Q,R,S$ の値は以下のとおりです。

  • 条件に該当する組が存在しないため $P=0$
  • 組 $(1,3),(2,3)$ が条件に該当するため $Q=2$
  • 組 $(1,3),(2,3)$ が条件に該当するため $R=2$
  • 組 $(1,2),(1,3),(2,3)$ が条件に該当するため $S=3$

したがって、求める値は $\frac{0-2}{\sqrt{2\times3}}=-\frac{2}{\sqrt{6}}=0.816496...$ となります。

サンプル2
入力
2
1 1
2 2
出力
1.0000000000000000

サンプル3
入力
5
4 4
5 7
0 4
2 10
-6 4
出力
0.3585685828003181

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。