結果

問題 No.3001 ヘビ文字列
ユーザー addeight2addeight2
提出日時 2024-12-22 20:52:00
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,610 bytes
コンパイル時間 2,100 ms
コンパイル使用メモリ 173,572 KB
実行使用メモリ 41,448 KB
最終ジャッジ日時 2025-01-01 07:36:32
合計ジャッジ時間 168,220 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,636 KB
testcase_01 AC 2 ms
13,764 KB
testcase_02 AC 2 ms
13,644 KB
testcase_03 AC 2 ms
13,764 KB
testcase_04 AC 2 ms
13,640 KB
testcase_05 AC 4 ms
26,444 KB
testcase_06 AC 4 ms
13,636 KB
testcase_07 AC 4 ms
26,656 KB
testcase_08 AC 3 ms
13,636 KB
testcase_09 AC 4 ms
25,816 KB
testcase_10 AC 4 ms
13,636 KB
testcase_11 AC 4 ms
26,756 KB
testcase_12 AC 4 ms
13,640 KB
testcase_13 AC 4 ms
26,376 KB
testcase_14 AC 4 ms
13,640 KB
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 AC 69 ms
41,448 KB
testcase_26 AC 67 ms
28,916 KB
testcase_27 AC 68 ms
40,656 KB
testcase_28 AC 68 ms
29,564 KB
testcase_29 AC 68 ms
28,928 KB
testcase_30 AC 68 ms
28,864 KB
testcase_31 AC 68 ms
41,052 KB
testcase_32 AC 68 ms
28,136 KB
testcase_33 AC 70 ms
40,424 KB
testcase_34 AC 70 ms
28,272 KB
testcase_35 TLE -
testcase_36 TLE -
testcase_37 TLE -
testcase_38 TLE -
testcase_39 TLE -
testcase_40 TLE -
testcase_41 TLE -
testcase_42 TLE -
testcase_43 TLE -
testcase_44 TLE -
testcase_45 TLE -
testcase_46 TLE -
testcase_47 TLE -
testcase_48 TLE -
testcase_49 TLE -
testcase_50 TLE -
testcase_51 TLE -
testcase_52 TLE -
testcase_53 TLE -
testcase_54 TLE -
testcase_55 TLE -
testcase_56 TLE -
testcase_57 TLE -
testcase_58 TLE -
testcase_59 TLE -
testcase_60 TLE -
testcase_61 TLE -
testcase_62 TLE -
testcase_63 TLE -
testcase_64 TLE -
testcase_65 TLE -
testcase_66 TLE -
testcase_67 TLE -
testcase_68 TLE -
testcase_69 TLE -
testcase_70 TLE -
testcase_71 TLE -
testcase_72 TLE -
testcase_73 TLE -
testcase_74 TLE -
testcase_75 TLE -
testcase_76 TLE -
testcase_77 TLE -
testcase_78 TLE -
testcase_79 TLE -
testcase_80 TLE -
testcase_81 TLE -
testcase_82 TLE -
testcase_83 TLE -
testcase_84 TLE -
testcase_85 AC 2 ms
6,820 KB
testcase_86 AC 2 ms
33,964 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, a) FOR(i, 0, a)

using namespace std;

vector<int> get_p_factors(int n) {
    vector<int> p_factors;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            p_factors.push_back(i);
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n != 1) {
        p_factors.push_back(n);
    }
    return p_factors;
}

pair<int, string> solve_w_period(string S, int period) {
    int n = S.length(), ans = 0;
    vector<int> char_cnt_vec(n, 0);
    REP(i, period) {
        pair<char, int> max_cnt;
        REP(j, n / period) {
            ++char_cnt_vec[S[i + period * j] - 'A'];
        }
        int max_ele = max_element(char_cnt_vec.begin(), char_cnt_vec.end())
                        - char_cnt_vec.begin();
        max_cnt.first = 'A' + max_ele;
        max_cnt.second = char_cnt_vec[max_ele];
        fill(char_cnt_vec.begin(), char_cnt_vec.end(), 0);
        ans += n / period - max_cnt.second;
        REP(j, n / period) {
            S[i + period * j] = max_cnt.first;
        }
    }
    return make_pair(ans, S);
}

string solve(string S) {
    int n = S.length();
    vector<int> p_factors = get_p_factors(n);

    auto ans = make_pair(n, S);
    for (int p_factor : p_factors) {
        int period = n / p_factor;
        auto temp_ans = solve_w_period(S, period);
        if (temp_ans.first < ans.first) {
            ans = temp_ans;
        }
    }
    return ans.second;
}

int main() {
    string S;
    cin >> S;
    cout << solve(S) << endl;
}
0