問題一覧 > 通常問題

No.852 Contiguous Substrings

レベル : / 実行時間制限 : 1ケース 3.153秒 / メモリ制限 : 315 MB / 小数誤差許容問題　絶対誤差または相対誤差が $10^{-5}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : （AC するまで非表示） / 解いたユーザー数 188
作問者 : CuriousFairy315 / テスター : tempura_pp
お気に入りにしたユーザー ProblemId : 2854 / 自分の提出
問題文最終更新日: 2019-07-13 03:22:13
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
yukicoder contest 218 (順位表) の他の問題:

Problem Statement

You are given a string $S$.
Find the average number of distinct characters over the non-empty contiguous substrings of $S$.

Input

$S$

$1 \leq |S| \leq 10^6$
$S$ consists only of lowercase English letters.

Output

Output the average number of distinct characters. An absolute error of up to $10^{-5}$ is allowed.
Print a newline at the end.

Sample

Sample 1
Input
ei
Output
1.33333

The non-empty contiguous substrings of ei are the 3 strings e, i, and ei, whose numbers of distinct characters are $1$, $1$, $2$, respectively.
Therefore, the answer is $\frac{1+1+2}{3}=\frac{4}{3} \fallingdotseq 1.33333 \cdots$.

Sample 2
Input
fairy
Output
2.33333

Sample 3
Input
temhomu
Output
2.78571

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