結果
問題 |
No.852 連続部分文字列
|
ユーザー |
![]() |
提出日時 | 2019-07-26 21:42:11 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 33 ms / 3,153 ms |
コード長 | 668 bytes |
コンパイル時間 | 598 ms |
コンパイル使用メモリ | 64,240 KB |
実行使用メモリ | 16,036 KB |
最終ジャッジ日時 | 2024-07-02 06:50:18 |
合計ジャッジ時間 | 1,981 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <stdio.h> #include <stdlib.h> #define llint long long using namespace std; string s; vector<llint> vec[26]; int main(void) { cin >> s; llint n = s.size(); s = "#" + s; for(int i = 0; i < 26; i++) vec[i].push_back(0); for(int i = 1; i <= n; i++){ vec[s[i]-'a'].push_back(i); } for(int i = 0; i < 26; i++) vec[i].push_back(n+1); llint ans = 0; for(int i = 0; i < 26; i++){ ans += n*(n+1)/2; for(int j = 1; j < vec[i].size(); j++){ llint len = vec[i][j]-vec[i][j-1]-1; ans -= len*(len+1)/2; } } printf("%.11f\n", (double)ans / (n*(n+1)/2)); return 0; }