結果

問題 No.3001 ヘビ文字列
ユーザー addeight2
提出日時 2025-01-13 09:29:54
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,448 bytes
コンパイル時間 687 ms
コンパイル使用メモリ 11,904 KB
実行使用メモリ 72,240 KB
最終ジャッジ日時 2025-01-13 09:33:31
合計ジャッジ時間 215,654 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 13 TLE * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

import numpy as np


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
    period_S = []
    for i in range(period):
        char_cnt = np.zeros(26)
        for j in range(n // period):
            char_cnt[ord(S[i + period * j]) - ord('A')] += 1
        if return_str:
            period_S.append(chr(ord('A') + np.argmax(char_cnt)))
        else:
            ans += n // period - np.max(char_cnt)
    if return_str:
        return ''.join(period_S)
    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
    period_S = solve_period(S, best_period, True)
    return period_S, n // best_period


S = input()
period_S, rep = solve(S)
for _ in range(rep):
    print(period_S, end='')
print()
0