結果

問題 No.852 連続部分文字列
ユーザー aya_seaya_se
提出日時 2019-07-26 22:36:46
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 100 ms / 3,153 ms
コード長 3,880 bytes
コンパイル時間 948 ms
コンパイル使用メモリ 101,484 KB
実行使用メモリ 7,836 KB
最終ジャッジ日時 2024-07-02 08:01:39
合計ジャッジ時間 3,416 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 4 ms
6,940 KB
testcase_14 AC 3 ms
6,944 KB
testcase_15 AC 4 ms
6,940 KB
testcase_16 AC 4 ms
6,944 KB
testcase_17 AC 5 ms
6,944 KB
testcase_18 AC 5 ms
6,940 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 4 ms
6,944 KB
testcase_21 AC 5 ms
6,944 KB
testcase_22 AC 3 ms
6,940 KB
testcase_23 AC 4 ms
6,940 KB
testcase_24 AC 3 ms
6,940 KB
testcase_25 AC 4 ms
6,944 KB
testcase_26 AC 4 ms
6,940 KB
testcase_27 AC 3 ms
6,940 KB
testcase_28 AC 4 ms
6,944 KB
testcase_29 AC 5 ms
6,944 KB
testcase_30 AC 2 ms
6,940 KB
testcase_31 AC 5 ms
6,944 KB
testcase_32 AC 5 ms
6,940 KB
testcase_33 AC 95 ms
6,940 KB
testcase_34 AC 97 ms
6,940 KB
testcase_35 AC 97 ms
6,944 KB
testcase_36 AC 95 ms
6,940 KB
testcase_37 AC 96 ms
6,944 KB
testcase_38 AC 96 ms
6,944 KB
testcase_39 AC 95 ms
6,940 KB
testcase_40 AC 97 ms
6,940 KB
testcase_41 AC 95 ms
6,940 KB
testcase_42 AC 79 ms
6,944 KB
testcase_43 AC 100 ms
7,836 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:185:25: warning: 'key' may be used uninitialized [-Wmaybe-uninitialized]
  185 |                         if (S[j] == key) {
      |                         ^~
main.cpp:155:22: note: 'key' was declared here
  155 |                 char key;
      |                      ^~~

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vll = vector<vl>;
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define REPR(i,n) for(int i=n-1; i>=(int)(0); i--)
#define FOR(i,a,b) for(int i=(int)(a); i<(int)(b); i++)
#define FORR(i,a,b) for(int i=(int)(b)-1; i>=(int)(a); i--)
#define CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))
#define ALL(v) (v).begin(),(v).end()
//**関数リスト**//
int ctoi(char c) {
	switch (c) {
	case '0': return 0;
	case '1': return 1;
	case '2': return 2;
	case '3': return 3;
	case '4': return 4;
	case '5': return 5;
	case '6': return 6;
	case '7': return 7;
	case '8': return 8;
	case '9': return 9;
	default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.second < secondElof.second;
}
ll nod(ll F) {
	ll keta = 1;
	while (F / 10 > 0) {
		keta++;
		F /= 10;
	}
	return keta;
}
ll gcd(ll x, ll y) {
	ll r;
	if (x < y) {
		swap(x, y);
	}
	while (y > 0) {
		r = x % y;
		x = y;
		y = r;
	}
	return x;
}
ll lcm(ll x, ll y) {
	return x * y / gcd(x, y);
}
ll isPrime(ll x) {
	ll i;
	if (x < 2) {
		return 0;
	}
	else if (x == 2) {
		return 1;
	}
	else if (x % 2 == 0) {
		return 0;
	}
	else {
		for (i = 3; i * i <= x; i += 2) {
			if (x % 1 == 0) {
				return 0;
			}
		}
		return 1;
	}
}
void eratos(vl isPrime) {
	//(注)isPrimeのサイズはN+1にする！実際にはmain内に配置して使用
	ll i, j;
	REP(i, isPrime.size()) {
		isPrime[i] = 1;
	}
	isPrime[0] = 0; isPrime[1] = 0;
	for (i = 2; i * i <= isPrime.size() - 1; i++) {
		if (isPrime[i] == 1) {
			j = i * 2;
			while (j <= isPrime.size() - 1) {
				isPrime[j] = 0;
				j = j + i;
			}
		}
	}
}
ll modinv(ll a, ll m) {
	ll b = m, u = 1, v = 0;
	while (b) {
		ll t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
void bitSearch(ll n) {
	//実際にはコピーして中身を改変して使う
	ll i;
	REP(i, pow(2, n)) {
		ll p = i;
		REP(i, n) {
			cout << p % 2;
			p /= 2;
		}
		cout << endl;
	}
}

void bfs(ll now) {
	//中身は毎回書き換えて使用
	queue<ll> Q;
	Q.push(now);
	ll u;
	while (!Q.empty()) {
		u = Q.front();
		Q.pop();
		//ll v=;
		//Q.push(v);
	}
}
//**定義場所**//
ll i, j, k, l, m, n;
ll N, M, K, H, W;
ll MOD = 1000000007;
double ans = 0;
//***********//

int main() {
	string S;
	cin >> S;
	N = S.length();
	double kazu = 0;
	for (i = 1; i <= N; i++) {
		kazu += N - i + 1;
	}
	for (i = 0; i < 26; i++) {
		char key;
		ll B = 0;
		if (i == B) { key = 'a'; }B++;
		if (i == B) { key = 'b'; }B++;
		if (i == B) { key = 'c'; }B++;
		if (i == B) { key = 'd'; }B++;
		if (i == B) { key = 'e'; }B++;
		if (i == B) { key = 'f'; }B++;
		if (i == B) { key = 'g'; }B++;
		if (i == B) { key = 'h'; }B++;
		if (i == B) { key = 'i'; }B++;
		if (i == B) { key = 'j'; }B++;
		if (i == B) { key = 'k'; }B++;
		if (i == B) { key = 'l'; }B++;
		if (i == B) { key = 'm'; }B++;
		if (i == B) { key = 'n'; }B++;
		if (i == B) { key = 'o'; }B++;
		if (i == B) { key = 'p'; }B++;
		if (i == B) { key = 'q'; }B++;
		if (i == B) { key = 'r'; }B++;
		if (i == B) { key = 's'; }B++;
		if (i == B) { key = 't'; }B++;
		if (i == B) { key = 'u'; }B++;
		if (i == B) { key = 'v'; }B++;
		if (i == B) { key = 'w'; }B++;
		if (i == B) { key = 'x'; }B++;
		if (i == B) { key = 'y'; }B++;
		if (i == B) { key = 'z'; }
		vl K;
		for (j = 0; j < N; j++) {
			if (S[j] == key) {
				K.push_back(j);
			}
		}
		if (K.size() != 0) {
			for (j = 0; j < K.size()-1; j++) {
				ans += (K[j] + 1) * (K[j + 1]-K[j]);
			}
			ans += (K[K.size() - 1]+1) * (N - K[K.size() - 1]);
		}
		K.clear();
	}
	cout << setprecision(10) << ans / kazu;
}
0