// 入力制約/フォーマットチェック(TL変更により元のバリデーションがTLEしたので再チェック) #ifndef INCLUDE_MODE #define INCLUDE_MODE // #define REACTIVE #define USE_GETLINE #endif #ifdef INCLUDE_MAIN void Solve() { GETLINE( S ); RUN( S , c ){ ASSERT( c , 'A' , 'Z' ); } int N = S.size(); CEXPR( int , bound_N , 2e6 ); ASSERT( N , 2 , bound_N ); constexpr PrimeEnumeration<1415> pe{}; auto [pf,e] = PrimeFactorisation( pe , N ); int p_best = -1; int opt = N + 1; RUN( pf , p ){ int d = N / p; int opt_temp = 0; FOR( i , 0 , d ){ vector h( 26 ); int temp = 0; FOR( j , 0 , p ){ temp = max( temp , ++h[S[i+j*d] - 'A'] ); } opt_temp += p - temp; } if( opt > opt_temp ){ opt = opt_temp; p_best = p; } CERR( "p,opt_temp =" , p , opt_temp ); } CERR( "p_best =" , p_best ); int d = N / p_best; FOR( i , 0 , d ){ vector h( 26 ); FOR( j , 0 , p_best ){ h[S[i+j*d] - 'A']++; } int c_opt = -1; int temp = 0; FOR( c , 0 , 26 ){ if( temp < h[c] ){ temp = h[c]; c_opt = c; } } FOR( j , 0 , p_best ){ S[i+j*d] = c_opt + 'A'; } } RETURN( S ); } REPEAT_MAIN(1); #else // INCLUDE_MAIN #ifdef INCLUDE_LIBRARY // https://github.com/p-adic/cpp // VVV ライブラリは以下に挿入する。redefinitionを避けるため圧縮元はincludeしない。 /* 圧縮用 */ #define TE template #define TY typename #define US using #define ST static #define AS assert #define IN inline #define CL class #define PU public #define OP operator #define CE constexpr #define CO const #define NE noexcept #define RE return #define WH while #define VO void #define VE vector #define LI list #define BE begin #define EN end #define SZ size #define LE length #define PW Power #define MO move #define TH this #define CRI CO int& #define CRUI CO uint& #define CRL CO ll& #define VI virtual #define IS basic_istream #define OS basic_ostream #define ST_AS static_assert #define reMO_CO remove_const #define is_COructible_v is_constructible_v #define rBE rbegin // PrimeEnumeration: // val_limit = 316 ≒ sqrt(1e5) -> length = 65 // val_limit = 448 ≒ sqrt(2e5) -> length = 86 // val_limit = 1e5 -> length = 9592 // val_limit = 1e6 -> length = 78498 // nの素因数分解:PrimeFactorisation(CO PE/LD& pe,CO INT& n) O(√n/log n)/O(log n) // nの素羃への分解:PrimePowerFactorisation(CO PE/LD& pe,CO INT& n) O(√n/log n)/O(log n) // CountDivisor( n ): // n <= 1e3 -> answer <= 32 // n <= 1e4 -> answer <= 64 // n <= 1e5 -> answer <= 128 // n <= 1e6 -> answer <= 256 // nの約数数え上げ:CountDivisor(CO PE/LD& pe,INT n) O(√n/log n)/O(log n) // nの約数辞書順列挙:EnumerateDivisor(CO PE/LD& pe,INT n) O(√n/log n)/O(log n/log log n) // SZ未満の数の約数全列挙:TotalEnumerateDivisor(CRI SZ(,FUNC f,U init)) O(size log size) TE CL PrimeEnumeration{PU:bool m_is_composite[val_limit];int m_val[le_max];int m_le;CE PrimeEnumeration();IN CRI OP[](CRI i)CO;CE CRI Get(CRI i)CO;CE CO bool& IsComposite(CRI n)CO;CE CRI length()CO NE;}; TE CE PrimeEnumeration::PrimeEnumeration():m_is_composite(),m_val(),m_le(0){for(int i = 2;i < val_limit;i++){if(! m_is_composite[i]){if(i <=(val_limit - 1)/ i){for(int j = i * i;j < val_limit;j += i){m_is_composite[j]= true;}}m_val[m_le++]= i;if(m_le >= le_max){break;}}}}TE IN CRI PrimeEnumeration::OP[](CRI i)CO{AS(0 <= i && i < m_le);RE m_val[i];}TE CE CRI PrimeEnumeration::Get(CRI i)CO{RE m_val[i];}TE CE CO bool& PrimeEnumeration::IsComposite(CRI n)CO{RE m_is_composite[n];}TE CE CRI PrimeEnumeration::length()CO NE{RE m_le;} CL HeapPrimeEnumeration{PU:int m_val_limit;VE m_is_composite;VE m_val;int m_le;IN HeapPrimeEnumeration(CRI val_limit);IN CRI OP[](CRI i)CO;IN CRI Get(CRI i)CO;IN bool IsComposite(CRI n)CO;IN CRI length()CO NE;}; IN HeapPrimeEnumeration::HeapPrimeEnumeration(CRI val_limit):m_val_limit(val_limit),m_is_composite(m_val_limit),m_val(),m_le(0){for(int i = 2;i < m_val_limit;i++){if(! m_is_composite[i]){if(i <=(m_val_limit - 1)/ i){for(int j = i * i;j < val_limit;j += i){m_is_composite[j]= true;}}m_val.push_back(i);}}m_le = m_val.SZ();}IN CRI HeapPrimeEnumeration::OP[](CRI i)CO{AS(0 <= i && i < m_le);RE m_val[i];}IN CRI HeapPrimeEnumeration::Get(CRI i)CO{RE OP[](i);}IN bool HeapPrimeEnumeration::IsComposite(CRI n)CO{AS(0 <= n && n < m_val_limit);RE m_is_composite[n];}IN CRI HeapPrimeEnumeration::length()CO NE{RE m_le;} TE auto CheckPE(CO PE& pe)-> decltype(pe.IsComposite(0),true_type());TE false_type CheckPE(...);TE CE bool IsPE = decltype(CheckPE(declval()))(); TE CL LeastDivisor{PU:int m_val[val_limit];CE LeastDivisor()NE;IN CRI OP[](CRI i)CO;CE CRI Get(CRI i)CO;CE int length()CO NE;}; TE CE LeastDivisor::LeastDivisor()NE:m_val{}{for(int d = 2;d < val_limit;d++){if(m_val[d]== 0){for(int n = d;n < val_limit;n += d){m_val[n]== 0?m_val[n]= d:d;}}}}TE IN CRI LeastDivisor::OP[](CRI i)CO{AS(0 <= i && i < val_limit);RE m_val[i];}TE CE CRI LeastDivisor::Get(CRI i)CO{RE m_val[i];}TE CE int LeastDivisor::length()CO NE{RE val_limit;} CL HeapLeastDivisor{PU:int m_val_limit;VE m_val;IN HeapLeastDivisor(CRI val_limit)NE;IN CRI OP[](CRI i)CO;IN CRI Get(CRI i)CO;IN CRI length()CO NE;}; IN HeapLeastDivisor::HeapLeastDivisor(CRI val_limit)NE:m_val_limit(val_limit),m_val(m_val_limit){for(int d = 2;d < m_val_limit;d++){if(m_val[d]== 0){for(int n = d;n < m_val_limit;n += d){m_val[n]== 0?m_val[n]= d:d;}}}}IN CRI HeapLeastDivisor::OP[](CRI i)CO{AS(0 <= i && i < m_val_limit);RE m_val[i];}IN CRI HeapLeastDivisor::Get(CRI i)CO{RE m_val[i];}IN CRI HeapLeastDivisor::length()CO NE{RE m_val_limit;} TE auto PrimeFactorisation(CO PE& pe,INT n)-> enable_if_t,pair,VE>>{AS(n > 0);VE P{};VE E{};CRI le = pe.length();for(int i = 0;i < le;i++){auto& p = pe[i];if(n % p == 0){int e = 1;WH((n /= p)% p == 0){e++;}P.push_back(p);E.push_back(e);}else if(n / p < p){break;}}if(n != 1){P.push_back(n);E.push_back(1);}RE{MO(P),MO(E)};}TE auto PrimeFactorisation(CO LD& ld,int n)-> enable_if_t,pair,VE>>{AS(n > 0);VE P{};VE E{};if(n > 1){P.push_back(ld[n]);E.push_back(1);n /= ld[n];}WH(n > 1){if(P.back()!= ld[n]){P.push_back(ld[n]);E.push_back(1);}else{E.back()++;}n /= ld[n];}RE{MO(P),MO(E)};}TE auto PrimePowerFactorisation(CO PE& pe,INT n)-> enable_if_t,tuple,VE,VE>>{AS(n > 0);VE P{};VE E{};VE Q{};CRI le = pe.length();for(int i = 0;i < le;i++){auto& p = pe[i];if(n % p == 0){int e = 1;INT q = p;WH((n /= p)% p == 0){e++;q *= p;}P.push_back(p);E.push_back(e);Q.push_back(q);}else if(n / p < p){break;}}if(n != 1){P.push_back(n);E.push_back(1);Q.push_back(n);}RE{MO(P),MO(E),MO(Q)};}TE auto PrimePowerFactorisation(CO LD& ld,int n)-> enable_if_t,tuple,VE,VE>>{AS(n > 0);VE P{};VE E{};VE Q{};if(n > 1){P.push_back(ld[n]);E.push_back(1);Q.push_back(ld[n]);n /= ld[n];}WH(n > 1){if(P.back()!= ld[n]){P.push_back(ld[n]);E.push_back(1);Q.push_back(ld[n]);}else{Q.back()*= ld[n];E.back()++;}n /= ld[n];}RE{MO(P),MO(E),MO(Q)};} TE INT CountDivisorBody(VE& E)NE{CO int LE = E.SZ();INT AN = 1;for(int i = 0;i < LE;i++){AN *= ++E[i];}RE AN;}TE INT CountDivisor(CO PE& pe,INT n)NE{auto[P,E]= PrimeFactorisation(pe,MO(n));RE CountDivisorBody(E);} TE VE EnumerateDivisorBody(CO VE& P,VE& E){CO int le = P.SZ();VE AN(CountDivisorBody(E),INT(1));int SZ = 1;for(int i = 0;i < le;i++){auto& P_i = P[i];auto& E_i = E[i];INT q = 1;int j_shift = 0;for(int e = 1;e < E_i;e++){q *= P_i;j_shift += SZ;for(int j = 0;j < SZ;j++){AN[j + j_shift]= AN[j]* q;}}SZ *= E_i;}RE AN;}TE auto EnumerateDivisor(CO PE& pe,INT n)-> enable_if_t,VE>{auto[P,E]= PrimeFactorisation(pe,MO(n));RE EnumerateDivisorBody(P,E);}TE auto EnumerateDivisor(CO LD& ld,INT n)-> enable_if_t,VE>{VE P{};VE E{};WH(n > 1){auto& p = ld[n];int e = 1;WH((n /= p)% p == 0){e++;}P.push_back(p);E.push_back(e);}RE EnumerateDivisorBody(P,E);}TE VE> TotalEnumerateDivisor(CO INT& SZ)NE{VE> AN(SZ);for(INT d = 1;d < SZ;d++){for(INT n = 0;n < SZ;n += d){AN[n].push_back(d);}}RE AN;}TE VE TotalEnumerateDivisor(CO INT& SZ,FUNC f,CO U& init)NE{ST_AS(is_invocable_r_v);VE AN(SZ,init);for(INT d = 1;d < SZ;d++){for(INT n = 0;n < SZ;n += d){AN[n]= f(MO(AN[n]),d);}}RE AN;} // AAA ライブラリは以上に挿入する。 #define INCLUDE_MAIN #include __FILE__ #else // INCLUDE_LIBRARY #ifdef DEBUG #define _GLIBCXX_DEBUG #define DEXPR( LL , BOUND , VALUE1 , VALUE2 ) CEXPR( LL , BOUND , VALUE2 ) #define SIGNAL signal( SIGABRT , &AlertAbort ); #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック: " , ( MIN ) , ( ( MIN ) <= A ? "<=" : ">" ) , A , ( A <= ( MAX ) ? "<=" : ">" ) , ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) ) #define COUT( ... ) VariadicCout( cout << "出力:" , __VA_ARGS__ ) << endl #define COUTNS( ... ) VariadicCoutNonSep( cout , __VA_ARGS__ ) << flush #define CERR( ... ) VariadicCout( cerr , __VA_ARGS__ ) << endl #define CERRNS( ... ) VariadicCout( cerr , __VA_ARGS__ ) << flush #define COUT_A( A , N ) OUTPUT_ARRAY( cout << "出力:" , A , N ) << endl #define CERR_A( A , N ) OUTPUT_ARRAY( cerr , A , N ) << endl int exec_mode = 0; #else #pragma GCC optimize ( "O3" ) #pragma GCC optimize ( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #define SIGNAL #define DEXPR( LL , BOUND , VALUE1 , VALUE2 ) CEXPR( LL , BOUND , VALUE1 ) #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) ) #define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << ENDL #define COUTNS( ... ) VariadicCoutNonSep( cout , __VA_ARGS__ ) #define CERR( ... ) #define CERRNS( ... ) #define COUT_A( A , N ) OUTPUT_ARRAY( cout , A , N ) << ENDL #define CERR_A( A , N ) #endif #ifdef REACTIVE #ifdef DEBUG #define RSET( A , ... ) A = __VA_ARGS__ #else #define RSET( A , ... ) cin >> A #endif #define RCIN( LL , A , ... ) LL A; RSET( A , __VA_ARGS__ ) #define ENDL endl #else #define ENDL "\n" #endif #ifdef USE_GETLINE #define SET_LL( A ) { GETLINE( A ## _str ); A = stoll( A ## _str ); } #define GETLINE_SEPARATE( SEPARATOR , ... ) string __VA_ARGS__; VariadicGetline( cin , SEPARATOR , __VA_ARGS__ ) #define GETLINE( ... ) GETLINE_SEPARATE( '\n' , __VA_ARGS__ ) #else #define SET_LL( A ) cin >> A #define CIN( LL , ... ) LL __VA_ARGS__; VariadicCin( cin , __VA_ARGS__ ) #define SET_A( I , N , ... ) VariadicResize( N + I , __VA_ARGS__ ); FOR( VARIABLE_FOR_SET_A , 0 , N ){ VariadicSet( cin , VARIABLE_FOR_SET_A + I , __VA_ARGS__ ); } #define CIN_A( LL , I , N , ... ) vector __VA_ARGS__; SET_A( I , N , __VA_ARGS__ ) #define CIN_AA( LL , I0 , N0 , I1 , N1 , VAR ) vector> VAR( N0 + I0 ); FOR( VARIABLE_FOR_CIN_AA , 0 , N0 ){ SET_A( I1 , N1 , VAR[VARIABLE_FOR_CIN_AA + I0] ); } #endif #include using namespace std; #define REPEAT_MAIN( BOUND ) int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ); SIGNAL; CEXPR( int , bound_test_case_num , BOUND ); int test_case_num = 1; if constexpr( bound_test_case_num > 1 ){ CERR( "テストケースの個数を入力してください。" ); SET_ASSERT( test_case_num , 1 , bound_test_case_num ); } FOR( test_case , 0 , test_case_num ){ if constexpr( bound_test_case_num > 1 ){ CERR( "testcase" , test_case , ":" ); } Solve(); CERR( "" ); } CHECK_REDUNDANT_INPUT; } #define START_WATCH chrono::system_clock::time_point watch = chrono::system_clock::now() #define CURRENT_TIME static_cast( chrono::duration_cast( chrono::system_clock::now() - watch ).count() / 1000.0 ) #define CHECK_WATCH( TL_MS ) ( CURRENT_TIME < TL_MS - 100.0 ) #define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE #define SET_ASSERT( A , MIN , MAX ) SET_LL( A ); ASSERT( A , MIN , MAX ) #define SET_A_ASSERT( I , N , A , MIN , MAX ) FOR( VARIABLE_FOR_SET_A , 0 , N ){ SET_ASSERT( A[VARIABLE_FOR_SET_A + I] , MIN , MAX ); } #define SET_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX ) FOR( VARIABLE_FOR_SET_AA0 , 0 , N0 ){ FOR( VARIABLE_FOR_SET_AA1 , 0 , N1 ){ SET_ASSERT( A[VARIABLE_FOR_SET_AA0 + I0][VARIABLE_FOR_SET_AA1 + I1] , MIN , MAX ); } } #define CIN_ASSERT( A , MIN , MAX ) decldecay_t( MAX ) A; SET_ASSERT( A , MIN , MAX ) #define CIN_A_ASSERT( I , N , A , MIN , MAX ) vector A( N + I ); SET_A_ASSERT( I , N , A , MIN , MAX ) #define CIN_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX ) vector A( N0 + I0 , vector( N1 + I1 ) ); SET_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( decldecay_t( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define FOREQ( VAR , INITIAL , FINAL ) for( decldecay_t( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) #define FOREQINV( VAR , INITIAL , FINAL ) for( decldecay_t( INITIAL ) VAR = INITIAL ; VAR + 1 > FINAL ; VAR -- ) #define ITR( ARRAY ) auto begin_ ## ARRAY = ARRAY .BE() , itr_ ## ARRAY = begin_ ## ARRAY , end_ ## ARRAY = ARRAY .EN() #define FOR_ITR( ARRAY ) for( ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ ) #define RUN( ARRAY , ... ) for( auto&& __VA_ARGS__ : ARRAY ) #define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) #define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS ) #define RETURN( ... ) COUT( __VA_ARGS__ ); return // 型のエイリアス #define decldecay_t( VAR ) decay_t template using ret_t = decltype( declval()( declval()... ) ); template using inner_t = typename T::type; using uint = unsigned int; using ll = long long; using ull = unsigned long long; using ld = long double; using lld = __float128; template using T2 = pair; template using T3 = tuple; template using T4 = tuple; using path = pair; /* VVV 常設ライブラリの非圧縮版は以下に挿入する。*/ // Random ll GetRand( const int& Rand_min , const int& Rand_max ) { assert( Rand_min <= Rand_max ); ll answer = time( NULL ); return answer * rand() % ( Rand_max + 1 - Rand_min ) + Rand_min; } // Set #define DECLARATION_OF_HASH( ... ) \ struct hash<__VA_ARGS__> \ { \ \ inline size_t operator()( const __VA_ARGS__& n ) const; \ \ }; \ class is_ordered { private: is_ordered() = delete; template static constexpr auto Check( const T& t ) -> decltype( t < t , true_type() ); static constexpr false_type Check( ... ); public: template static constexpr const bool value = is_same_v< decltype( Check( declval() ) ) , true_type >; }; template using Set = conditional_t>,unordered_set,conditional_t,set,void>>; // Tuple #define DECLARATION_OF_ARITHMETIC_FOR_TUPLE( OPR ) \ template typename V> inline auto operator OPR ## =( V& t0 , const V& t1 ) -> decltype( ( get<0>( t0 ) , t0 ) )&; \ template inline tuple& operator OPR ## =( tuple& t0 , const tuple& t1 ); \ template inline tuple& operator OPR ## =( tuple& t0 , const tuple& t1 ); \ template typename V> inline auto operator OPR ## =( V& t0 , const ARG& t1 ) -> decltype( ( get<0>( t0 ) , t0 ) )&; \ template inline tuple& operator OPR ## =( tuple& t0 , const ARG& t1 ); \ template inline tuple& operator OPR ## =( tuple& t0 , const ARG& t1 ); \ template