結果

問題 No.3001 ヘビ文字列
ユーザー 白寧杰
提出日時 2025-01-07 12:03:44
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,255 bytes
コンパイル時間 1,187 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 325,556 KB
最終ジャッジ日時 2025-01-07 12:06:07
合計ジャッジ時間 125,541 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32 WA * 10 TLE * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env pypy3

def main():
    s = input()
    len_s = len(s)

    # len_s の約数をすべて求める (1 と len_s 自身は除外する)
    divisors = []
    i = 2
    while i * i <= len_s:
        if len_s % i == 0:
            divisors.append(i)
            if i != len_s // i:
                divisors.append(len_s // i)
        i += 1
    # 約数が小さい順に揃える
    divisors.sort()

    # 約数が 1 つも見つからなければ -> 素数とみなし s[0] * len_s を出力して終了
    if not divisors:
        print(s[0] * len_s)
        return

    # ここから先は約数がある前提で、元コードのロジックを適用
    min_execution = 10**15  # 適当に大きい数で初期化
    min_result = None

    for m in divisors:
        # m は len_s の約数なので割り切れる
        n = len_s // m

        # 各「列」(あるいはブロック位置) ごとに、もっとも頻度の高い文字を探す
        # A〜Z の文字が 26 種類だけなら配列長は 26 でOK (元コードでは 30 でしたが 26 で十分)
        unit_result = []
        for i in range(m):
            count_arr = [0] * 26
            for j in range(n):
                ch = s[j*m + i]
                count_arr[ord(ch) - 65] += 1
            # 最頻出文字 (出現回数が最大の文字) を求める
            max_count = -1
            max_char_idx = -1
            for idx, cnt in enumerate(count_arr):
                if cnt > max_count:
                    max_count = cnt
                    max_char_idx = idx
            # 文字に戻す
            unit_result.append(chr(max_char_idx + 65))

        # 求めた単位文字列を n 回繰り返す
        unit_str = "".join(unit_result)
        concat_unit = unit_str * n

        # 元の文字列との相違数をカウント
        diff = 0
        for i in range(len_s):
            if s[i] != concat_unit[i]:
                diff += 1

        # 差分が小さいものを最適解として記録
        if diff < min_execution:
            min_execution = diff
            min_result = concat_unit

    # 約数の中で最適解だった文字列を出力
    print(min_result)


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