結果
問題 |
No.852 連続部分文字列
|
ユーザー |
|
提出日時 | 2019-07-26 21:42:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 28 ms / 3,153 ms |
コード長 | 558 bytes |
コンパイル時間 | 1,961 ms |
コンパイル使用メモリ | 195,500 KB |
最終ジャッジ日時 | 2025-01-07 07:45:16 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h> #define FOR(i,k,n) for(int i = (k);i < (n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(x) begin(x),end(x) using namespace std; using vecint = vector<int>; using ll = int64_t; int main() { string s; cin>>s; ll n = s.size(); vecint old(26, -1); ll cnt = 26*n*(n+1)/2; REP(i,n) { ll d = i - old[s[i]-'a']; cnt -= d*(d-1)/2; old[s[i]-'a'] = i; } REP(i,26) { ll d = n - old[i]; cnt -= d*(d-1)/2; } double div = n*(n+1)/2; cout<<fixed<<setprecision(10)<<(cnt/div)<<endl; return 0; }