AtCoder Regular Contest 033

B - メタ構文変数


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

foo」や「bar」「hoge」などの、特に意味を持たない変数の名前に使用される文字列のことを「メタ構文変数」と呼びます。

高橋君は今、メタ構文変数について調べています。メタ構文変数には色々な種類があることが分かり、見つけたメタ構文変数にそれぞれに番号をつけました。高橋君はアリの Ant さんと Bug くんのソースコードを読み、それぞれのソースコードに現れるメタ構文変数の番号を列挙しました。そして、Ant さんと Bug くんの使うメタ構文変数の集合がどれくらい似ているのかを調べるために「Jaccard 係数」を計算することにしました。Ant さんのソースコードに現れるメタ構文変数の集合を S_ABug くんのソースコードに現れるメタ構文変数の集合を S_B とするとこれらの集合の Jaccard 係数は、

  • ||S_{A} ∩ S_{B}|| / ||S_{A} ∪ S_{B}||

という式で計算できます。ここで、||S|| は集合 S の要素数を表すものとします。別の言い方をすると、

  • S_{A}S_{B} の両方に現れる要素の個数」/S_{A}S_{B} の少なくともどちらか一方には現れる要素の個数」

となります。


入力

入力は以下の形式で標準入力から与えられる。

N_A N_B
A_1 A_2 ... A_{N_A}
B_1 B_2 ... B_{N_B}
  • 1 行目には、2 つの整数 N_A (1 ≦ N_A ≦ 10^5), N_B (1 ≦ N_B ≦ 10^5) が空白区切りで与えられる。これは、Ant さんのソースコードに N_A 個、Bug くんのソースコードに N_B 個のメタ構文変数が現れたということを表す。
  • 2 行目には、Ant さんのソースコードに現れたメタ構文変数の番号を表す N_A 個の整数が空白区切りで与えられる。このうち i 番目の整数 A_i (1 ≦ A_i ≦ 10^9) は、Ant さんのソースコードに A_i 番のメタ構文変数が現れることを表す。ただし、p \neq q のとき A_p \neq A_q であることが保証される。
  • 3 行目には、Bug くんのソースコードに現れたメタ構文変数の番号を表す N_B 個の整数が空白区切りで与えられる。このうち i 番目の整数 B_i (1 ≦ B_i ≦ 10^9) は、Bug さんのソースコードに B_i 番のメタ構文変数が現れることを表す。ただし、p \neq q のとき B_p \neq B_q であることが保証される。

部分点

この問題には部分点が設定されている。

  • N_A,N_B ≦ 1000A_i,B_i ≦ 10^5 を満たすテストケース全てに正解した場合は、40 点が与えられる。
  • A_i,B_i ≦ 10^5 を満たすテストケース全てに正解した場合は、70 点が与えられる。

出力

Ant さんと Bug くんのソースコードに現れるメタ構文変数の集合の Jaccard 係数を 1 行に出力せよ。小数点以下何桁でも出力してよいが、10^{-6} を超える絶対誤差を含んではならない。出力の末尾に改行を入れること。


入力例1

3 2
1 3 5
1 2

出力例1

0.2500000000

Ant さんと Bug くんのソースコードの両方に現れるメタ構文変数は 1 番のみで、Ant さんと Bug くんのソースコードの少なくともどちらか一方には現れるメタ構文変数は 1,2,3,5 番の 4 つです。

よって、Jaccard 係数は 1/4 となります。


入力例2

9 10
11 2 33 4 55 6 77 8 99
10 11 14 19 55 1000000000 4 5 7 8

出力例2

0.2666666667

Submit提出する