結果

問題 No.852 連続部分文字列
コンテスト
ユーザー LyricalMaestro
提出日時 2024-12-01 12:08:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,131 ms / 3,153 ms
コード長 867 bytes
コンパイル時間 307 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 77,696 KB
最終ジャッジ日時 2024-12-01 12:08:25
合計ジャッジ時間 15,982 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/852

MAX_VALUE = 10 ** 18

def main():
    S = input()

    min_alphabet_base = [MAX_VALUE] * 26
    answer = 0
    for i in range(len(S)):
        s = S[i]
        s_value = ord(s) - ord("a")

        min_alphabet_base[s_value] = i

        # 種類数計算
        min_alphabets = min_alphabet_base.copy()
        min_alphabets.sort()

        max_spiceses = 0
        for k in range(len(min_alphabets)):
            if min_alphabets[k] < MAX_VALUE:
                max_spiceses += 1

        prev_ = -1
        for k in range(len(min_alphabets)):
            i0 = min_alphabets[k]
            if i0 == MAX_VALUE:
                break

            answer += (i0 - prev_) * (max_spiceses - k)
            prev_ = i0
            
    n0 = (len(S) * (len(S) + 1)) // 2
    print(answer / n0)

if __name__ == "__main__":
    main()
0