結果

問題 No.3001 ヘビ文字列
ユーザー navel_tos
提出日時 2025-01-14 23:11:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,176 ms / 1,500 ms
コード長 3,476 bytes
コンパイル時間 666 ms
コンパイル使用メモリ 82,548 KB
実行使用メモリ 218,372 KB
最終ジャッジ日時 2025-01-14 23:12:26
合計ジャッジ時間 57,247 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 83
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder3001 ヘビ文字列

#愚直解  明らかにN - 1文字の変更でヘビ文字列になる点に注意
from itertools import product, combinations
def brute(T):
    #1. Tを種類圧縮
    N = len(T)
    P = sorted(set(T))
    Q = {Ti: i for i, Ti in enumerate(P)}
    T = [ Q[Ti] for Ti in T ]
    n = len(Q)  #出現する種類数

    #2. 気合いで全列挙  計算量はしらない
    for k in range(N):  #replace個数
        for B in combinations( range(N), r = k ):  #replace位置
            for C in product( range(n), repeat = k ):   #replace先
                S = T[:]
                for Bi, Ci in zip(B, C):
                    S[Bi] = Ci
                for t in range(1, N):  #S[t: t + N]とS[0: N]が一致するか判定
                    if all( S[i] == S[ (t + i) % N ] for i in range(N) ):
                        return k, S

#素因数分解
def factorial(N):
    F = []
    for n in range(2, N + 1):
        if n > N:
            break
        if ( N % n == 0 ) and ( c := 0 ) == 0:
            while N % n == 0 and ( c := c + 1 ):
                N //= n
            F.append((n, c))
    if N > 1:
        F.append((N, 1))
    return F

#約数列挙
def divisor(N):
    F = factorial(N)
    D = [1]
    for p, e in F:
        nD = []
        for n in D:
            nD.append( n * ( q := 1 )  )
            for _ in range(e):
                nD.append( n * ( q := q * p ) )
        D = nD
    D.sort()
    return D
            

#実験すると N = len(S) = 1441440 のとき、約数が最大で288個
#現在の解法は:
#for n in (Nの約数であって、Nでないもの):
#    c = N
#    for m in range(n):
#        c -= ( S[m], S[m + n], S[m + 2n], ･･･ の文字種のうち最大のもの )
#cが最小となるnが理想のswap量。あとはよしなに

#for n: (Nの約数全体) とすると Dn = 288 よりループ回数がきつい
#でも普通にnは大きい方がよくない？Nの素因数の1種類だけをノックダウンすればよいのでは
def solve(T):
    #丁寧にやらないとTLEするらしい こまった
    #1. 座標圧縮・Sへの変換
    A = [-1] * 26
    N = len(T)
    for i in range(N):
        A[ ord( T[i] ) - ord('A') ] += 1
    c = 0
    C = []
    for i in range(26):
        if A[i] != -1:
            A[i] = c
            c += 1
            C.append( chr( ord('A') + i ) )
    D = {Ti: i for i, Ti in enumerate(C)}
    S = [ A[ ord( T[i] ) - ord('A') ] for i in range(N) ]
    n = len(D)

    #2. swap量の候補を全探索し、replace数が最小となるswap量tを検索
    rep = N = len(T)
    rept = -1
    A = [0] * n  #種類数カウンター
    F = factorial(N)
    for Pi, Ei in F:
        c = N
        t = N // Pi

        #tだけswapする
        for m in range(t):
            for i in range(m, N, t):
                A[ S[i] ] += 1
            c -= max(A)
            for i in range(n):
                A[i] = 0
        if rep > c:
            rep, rept = c, t

    #3. reptだけswapすると決め打って最終構築
    for m in range( rept ):
        for i in range(m, N, rept):
            A[ S[i] ] += 1
        s = A.index( max(A) )
        for i in range(m, N, rept):
            S[i] = s
        for i in range(n):
            A[i] = 0

    #4. Sを復元
    for i in range(N):
        S[i] = C[ S[i] ]
    return ''.join(S)


#入力高速化
import sys
input = sys.stdin.readline

#実行
print( solve(input().strip()) )
0