E - Concentration Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

高橋君は神経衰弱のような 1 人ゲームで遊んでいます。

2N 枚のカードがあります。カードの表には数が 1 つ書かれており、カードの裏には何も書かれていません。
1 \leq i \leq N を満たす各 i について、A_i が書かれたカードはちょうど 2 枚あります。(A_i は相異なります)

高橋君はこれらのカードを使って次の手順でゲームを行います。

  • 2N 枚のカードを裏向きの状態でシャッフルし、場に並べる。
  • ライフ を L 、スコア を 0 とする。
  • ライフが 0 になるか、場のカードがなくなるまで以下を繰り返す。
    • 場の裏向きのカードを 1 枚選び表にし、書かれている数 X を確認する。
    • 場の裏向きのカードを 1 枚選び表にし、書かれている数 Y を確認する。
    • X=Y のとき、その 2 枚を場から取り除き、スコアを X 増やす。
    • X\neq Y のとき、2 枚のカードを再び裏向きに戻し、ライフを 1 減らす。

高橋君がゲーム時のスコアを最大化するように最適に行動したときの、ゲーム終了時のスコアの期待値を求めてください。

ゲームに関するより厳密な説明は以下の通りです。

  • 高橋君は、以下に述べるこのゲームのルールを知っている。
  • 高橋君は A_1,\dots,A_N の値を知っている。
  • 長さ 2N の列 (A_1,A_1,A_2,A_2,\ldots,A_N,A_N) の並び替えを一様ランダムに 1 つ取り B とする。
  • 最初、高橋君は B のどの値も知らない。高橋君は一度知った B_i の値をそれ以降完全に記憶する。
  • ライフを L 、スコアを 0 、 S を \{1,2,3,\ldots,2N\} とする。これらの値を高橋君は常に知っている。
  • ライフが 0 になるか、 S が空になるまで以下を繰り返す。
    • 高橋君はこの時点までに得られた情報に基づいて S から要素を 1 つ選択し i とする。
    • B_i の値が公開され、高橋君はその値を知る。
    • 高橋君はこの時点までに得られた情報(B_i の値を含む)に基づいて S\setminus\{i\} から要素を 1 つ選択し j とする。
    • B_j の値が公開され、高橋君はその値を知る。
    • B_i=B_j ならば、 S から i,j を取り除き、スコアに B_i を加算する。
    • B_i \neq B_j ならば、 ライフを 1 減らす。
  • 高橋君は、ゲーム終了時のスコアの期待値を最大化するように、最適に行動する。

制約

  • 1 \leq N \leq 200
  • 1 \leq L \leq 200
  • 1 \leq A_1 < A_2 < \dots < A_N \leq 10^5
  • 入力される値は全て整数

入力

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

N L
A_1 A_2 \dots A_N

出力

答えを出力せよ。
真の解との絶対誤差または相対誤差が 10^{-5} 以下であれば正解として扱われる。

入力例 1

3 2
1 2 3

出力例 1

3.8666666667

例えばゲームは次のように進行します。6 枚のカードを区別するために、A, B, C, D, E, F と呼ぶことにします。

  • ライフ 2 、スコア 0 でゲームを始める。
  • カード A を表にする。 3 が書かれている。
  • カード B を表にする。 2 が書かれている。
  • 異なる数が書かれているので、 2 枚とも裏に戻し、ライフを 1 減らして 1 とする。
  • カード C を表にする。 3 が書かれている。
  • カード A を表にする。 3 が書かれている。
  • 同じ数が書かれているので、 2 枚とも場から取り除き、スコアを 3 増やして 3 とする。
  • カード D を表にする。 1 が書かれている。
  • カード E を表にする。 2 が書かれている。
  • 異なる数が書かれているので、 2 枚とも裏に戻し、ライフを 1 減らして 0 とする。
  • ライフが 0 となったのでゲームを終了する。スコアは 3 である。

この進行におけるカード C を表にした直後の時点で、高橋君は「カード C の表に 3 が書かれていたことを受けて、既に知っている 3 が書かれているもう 1 枚のカード A を表にする」という判断が可能であることに注意してください。

入力例 2

5 2
2 3 5 7 101

出力例 2

17.8560846561

入力例 3

20 10
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200

出力例 3

770.7122293087

Score : 450 points

Problem Statement

Takahashi is playing a solitaire game similar to the memory-matching game.

There are 2N cards. A number is written on the front of each card, and nothing is written on the back.
For each i satisfying 1 \leq i \leq N, there are exactly two cards on which A_i is written. (The A_i are pairwise distinct.)

Takahashi plays the game with these cards using the following procedure.

  • Shuffle the 2N cards and lay them out face down.
  • Set life to L and score to 0.
  • Repeat the following until life becomes 0 or there are no cards left on the table:
    • Choose one face-down card on the table, turn it face up, and check the number X written on it.
    • Choose one face-down card on the table, turn it face up, and check the number Y written on it.
    • If X=Y, remove those two cards from the table, and increase the score by X.
    • If X\neq Y, turn the two cards face down again, and decrease life by 1.

Find the expected value of the score at the end of the game when Takahashi acts optimally to maximize the score at the end of the game.

Below is a more formal description of the game.

  • Takahashi knows the rules of this game described below.
  • Takahashi knows the values of A_1,\dots,A_N.
  • Let B be a sequence obtained by choosing a permutation of the length-2N sequence (A_1,A_1,A_2,A_2,\ldots,A_N,A_N) uniformly at random.
  • Initially, Takahashi knows none of the values of B. Once he learns the value of B_i, he remembers it completely thereafter.
  • Let life be L, score be 0, and S be \{1,2,3,\ldots,2N\}. Takahashi always knows these values.
  • Repeat the following until life becomes 0 or S becomes empty:
    • Based on the information obtained up to this point, Takahashi chooses an element from S, and calls it i.
    • The value of B_i is revealed, and Takahashi learns it.
    • Based on the information obtained up to this point (including the value of B_i), Takahashi chooses an element from S\setminus\{i\}, and calls it j.
    • The value of B_j is revealed, and Takahashi learns it.
    • If B_i=B_j, remove i and j from S, and add B_i to the score.
    • If B_i \neq B_j, decrease life by 1.
  • Takahashi acts optimally to maximize the expected value of the score at the end of the game.

Constraints

  • 1 \leq N \leq 200
  • 1 \leq L \leq 200
  • 1 \leq A_1 < A_2 < \dots < A_N \leq 10^5
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N L
A_1 A_2 \dots A_N

Output

Output the answer.
Your output will be considered correct if its absolute or relative error from the true answer is at most 10^{-5}.

Sample Input 1

3 2
1 2 3

Sample Output 1

3.8666666667

The game may proceed as follows, for example. To distinguish the six cards, let us call them A, B, C, D, E, F.

  • Start the game with life 2 and score 0.
  • Turn card A face up. 3 is written on it.
  • Turn card B face up. 2 is written on it.
  • Since different numbers are written, turn both cards face down again, and decrease life by 1 to 1.
  • Turn card C face up. 3 is written on it.
  • Turn card A face up. 3 is written on it.
  • Since the same number is written, remove both cards from the table, and increase the score by 3 to 3.
  • Turn card D face up. 1 is written on it.
  • Turn card E face up. 2 is written on it.
  • Since different numbers are written, turn both cards face down again, and decrease life by 1 to 0.
  • Since life has become 0, the game ends. The score is 3.

Note that, immediately after turning card C face up in this sequence, Takahashi can make the choice of "turning face up card A, the other already-known card with 3 written on it, based on the fact that 3 was written on the front of card C."

Sample Input 2

5 2
2 3 5 7 101

Sample Output 2

17.8560846561

Sample Input 3

20 10
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200

Sample Output 3

770.7122293087