結果

問題 No.852 連続部分文字列
コンテスト
ユーザー kuuso1
提出日時 2019-07-26 22:38:07
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,405 bytes
コンパイル時間 1,984 ms
コンパイル使用メモリ 177,840 KB
実行使用メモリ 13,880 KB
最終ジャッジ日時 2024-07-02 08:03:29
合計ジャッジ時間 10,269 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <bits/stdc++.h>
#include <time.h>
#include <sys/timeb.h>
#include <cstdio>
#include <sys/time.h>

using namespace std;
#define ll long long
#define uint unsigned int
#define ulong unsigned long long int

template<typename T> bool InRange(T t, T l, T r){ return l <= t && t < r; }
string S;
int N;

double calc(int len){
	map<char, int> dl;
	int l = 0;
	map<char, int> dr;
	int r = 0;
	double cnt = 0;
	for(int i=0;i<N;i++){
		if(l < i) l = i;
		if(r < i) r = i;
		while(l < N){
			if(dl.find(S[l]) != dl.end()){
				dl[S[l]]++;
				l++;
				continue;
			}
			if(dl.size() < len - 1){
				dl.insert(make_pair(S[l], 1));
				l++;
				continue;
			}
			break;
		}
		while(r < N){
			if(dr.find(S[r]) != dr.end()){
				dr[S[r]]++;
				r++;
				continue;
			}
			if(dr.size() < len){
				dr.insert(make_pair(S[r], 1));
				r++;
				continue;
			}
			break;
		}
		if(dr.size() == len){
			cnt += r - l;
		}
		if(dl.find(S[i]) != dl.end()){
			dl[S[i]]--;
			if(dl[S[i]] == 0) dl.erase(S[i]);
		}
		if(dr.find(S[i]) != dr.end()){
			dr[S[i]]--;
			if(dr[S[i]] == 0) dr.erase(S[i]);
		}
	}
	//Console.WriteLine("len:{0}, cnt:{1}",len, cnt);
	
	double tot = (double) N * (double) (N + 1) / 2.0;
	return (double) len * cnt / tot;
	
}






int main(){
	
	cin >> S;
	N = S.length();
	double ret = 0;
	for(int i=1;i<=26;i++){
		ret += calc(i);
	}
	printf("%.12f\n",ret);
	
    return 0;
}
0