結果

問題 No.3001 ヘビ文字列
ユーザー addeight2
提出日時 2024-12-31 08:59:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,386 ms / 1,500 ms
コード長 1,400 bytes
コンパイル時間 639 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 285,436 KB
最終ジャッジ日時 2025-01-01 07:49:37
合計ジャッジ時間 69,656 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 83
権限があれば一括ダウンロードができます

ソースコード

diff # 

def soinsuu_bunkai(n):
    soinsuu = []
    i = 2
    while i * i <= n:
        if n % i == 0:
            soinsuu.append(i)
            while n % i == 0:
                n //= i
        i += 1
    if n != 1:
        # root(n) までで割り切れなければ素数
        soinsuu.append(n)
    return soinsuu


def solve_period(S, period, return_str=False):
    # 周期が period の文字列にするためにかかるコストを返す
    # return_str = True のときは、その文字列を返す
    n = len(S)
    ans = 0
    S_prime = ['A'] * n
    for i in range(period):
        char_cnt = [0] * (ord('Z') - ord('A') + 1)
        for j in range(n // period):
            char_cnt[ord(S[i + period * j]) - ord('A')] += 1
        mx = max(char_cnt)
        if return_str:
            for j in range(n // period):
                S_prime[i + period * j] = chr(ord('A') + char_cnt.index(mx))
        else:
            ans += n // period - mx
    if return_str:
        return ''.join(S_prime)
    else:
        return ans


def solve(S):
    n = len(S)
    soinsuu_lst = soinsuu_bunkai(n)

    ans = n
    best_period = 1
    for soinsuu in soinsuu_lst:
        period = n // soinsuu
        temp_ans = solve_period(S, period)
        if temp_ans < ans:
            ans = temp_ans
            best_period = period
    return solve_period(S, best_period, True)


S = input()
print(solve(S))
0