結果
問題 | No.852 連続部分文字列 |
ユーザー | risujiroh |
提出日時 | 2019-07-26 21:40:09 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 927 ms / 3,153 ms |
コード長 | 1,582 bytes |
コンパイル時間 | 1,888 ms |
コンパイル使用メモリ | 171,880 KB |
実行使用メモリ | 234,688 KB |
最終ジャッジ日時 | 2023-09-15 00:52:00 |
合計ジャッジ時間 | 13,689 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,384 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,504 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,384 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,384 KB |
testcase_10 | AC | 1 ms
4,380 KB |
testcase_11 | AC | 1 ms
4,380 KB |
testcase_12 | AC | 2 ms
4,380 KB |
testcase_13 | AC | 14 ms
6,608 KB |
testcase_14 | AC | 8 ms
4,668 KB |
testcase_15 | AC | 23 ms
8,752 KB |
testcase_16 | AC | 15 ms
6,504 KB |
testcase_17 | AC | 21 ms
8,108 KB |
testcase_18 | AC | 25 ms
9,288 KB |
testcase_19 | AC | 3 ms
4,380 KB |
testcase_20 | AC | 12 ms
5,828 KB |
testcase_21 | AC | 25 ms
9,312 KB |
testcase_22 | AC | 9 ms
5,008 KB |
testcase_23 | AC | 18 ms
7,600 KB |
testcase_24 | AC | 10 ms
5,452 KB |
testcase_25 | AC | 17 ms
7,264 KB |
testcase_26 | AC | 25 ms
9,468 KB |
testcase_27 | AC | 16 ms
6,676 KB |
testcase_28 | AC | 20 ms
7,964 KB |
testcase_29 | AC | 26 ms
9,364 KB |
testcase_30 | AC | 5 ms
4,380 KB |
testcase_31 | AC | 27 ms
9,568 KB |
testcase_32 | AC | 28 ms
9,892 KB |
testcase_33 | AC | 914 ms
234,496 KB |
testcase_34 | AC | 907 ms
234,664 KB |
testcase_35 | AC | 904 ms
234,440 KB |
testcase_36 | AC | 927 ms
234,480 KB |
testcase_37 | AC | 907 ms
234,632 KB |
testcase_38 | AC | 901 ms
234,408 KB |
testcase_39 | AC | 911 ms
234,424 KB |
testcase_40 | AC | 913 ms
234,616 KB |
testcase_41 | AC | 915 ms
234,628 KB |
testcase_42 | AC | 738 ms
234,688 KB |
testcase_43 | AC | 843 ms
234,492 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using lint = long long; template<class T = int> using V = vector<T>; template<class T = int> using VV = V< V<T> >; struct DisjointSparseTable { using T = int; static T op(const T& x, const T& y) { return x | y; } const int n; VV<T> t; template<class Itr> DisjointSparseTable(Itr first, Itr last) : n(distance(first, last)), t(__lg(n) + 1, V<T>(first, last)) { for (int k = 1; k < (int) t.size(); ++k) { for (int i0 = 1 << k; i0 < n; i0 += 1 << k + 1) { for (int i = i0 + 1; i < min(i0 + (1 << k), n); ++i) { t[k][i] = op(t[k][i - 1], t[k][i]); } for (int i = i0 - 2; i >= i0 - (1 << k); --i) { t[k][i] = op(t[k][i], t[k][i + 1]); } } } } T acc(int l, int r) const { assert(l < r); if (l == --r) return t[0][l]; int k = __lg(l ^ r); return op(t[k][l], t[k][r]); } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); string s; cin >> s; int n = s.size(); V<> a(n); for (int i = 0; i < n; ++i) { a[i] = 1 << s[i] - 'a'; } DisjointSparseTable dst(begin(a), end(a)); VV<> b(n, V<>(27)); for (int k = 1; k <= 26; ++k) { int r = 0; for (int l = 0; l < n; ++l) { while (r < n and __builtin_popcount(dst.acc(l, r + 1)) <= k) ++r; b[l][k] = r; } } lint sum = 0; for (int l = 0; l < n; ++l) { b[l][0] = l; for (int k = 1; k <= 26; ++k) { sum += (b[l][k] - b[l][k - 1]) * k; } } cout << fixed << setprecision(15) << sum / (0.5 * n * (n + 1)) << '\n'; }