#1033893 (C++23) No.3001 ヘビ文字列

提出ソース

結果

問題	No.3001 ヘビ文字列
ユーザー	Flkanjin
提出日時	2025-01-01 12:40:02
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	644 ms / 1,500 ms
コード長	3,115 bytes
コンパイル時間	2,870 ms
コンパイル使用メモリ	202,224 KB
実行使用メモリ	144,408 KB
最終ジャッジ日時	2025-01-01 12:40:45
合計ジャッジ時間	37,346 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	3 ms 6,816 KB
testcase_04	AC	3 ms 6,816 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	AC	2 ms 6,816 KB
testcase_07	AC	3 ms 6,816 KB
testcase_08	AC	3 ms 6,816 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	AC	2 ms 6,820 KB
testcase_11	AC	3 ms 6,816 KB
testcase_12	AC	2 ms 6,820 KB
testcase_13	AC	2 ms 6,816 KB
testcase_14	AC	2 ms 6,820 KB
testcase_15	AC	393 ms 144,408 KB
testcase_16	AC	429 ms 143,212 KB
testcase_17	AC	388 ms 143,228 KB
testcase_18	AC	388 ms 142,812 KB
testcase_19	AC	396 ms 143,456 KB
testcase_20	AC	395 ms 143,952 KB
testcase_21	AC	392 ms 143,332 KB
testcase_22	AC	395 ms 144,304 KB
testcase_23	AC	394 ms 143,120 KB
testcase_24	AC	397 ms 143,132 KB
testcase_25	AC	63 ms 7,244 KB
testcase_26	AC	63 ms 8,036 KB
testcase_27	AC	63 ms 7,832 KB
testcase_28	AC	63 ms 7,808 KB
testcase_29	AC	63 ms 7,248 KB
testcase_30	AC	62 ms 7,252 KB
testcase_31	AC	63 ms 8,736 KB
testcase_32	AC	62 ms 7,248 KB
testcase_33	AC	62 ms 7,700 KB
testcase_34	AC	63 ms 7,244 KB
testcase_35	AC	55 ms 7,248 KB
testcase_36	AC	58 ms 8,316 KB
testcase_37	AC	57 ms 8,368 KB
testcase_38	AC	56 ms 8,044 KB
testcase_39	AC	56 ms 8,184 KB
testcase_40	AC	56 ms 7,376 KB
testcase_41	AC	58 ms 8,084 KB
testcase_42	AC	55 ms 7,244 KB
testcase_43	AC	56 ms 7,700 KB
testcase_44	AC	56 ms 7,852 KB
testcase_45	AC	573 ms 139,532 KB
testcase_46	AC	556 ms 139,472 KB
testcase_47	AC	563 ms 139,556 KB
testcase_48	AC	560 ms 139,468 KB
testcase_49	AC	561 ms 139,500 KB
testcase_50	AC	548 ms 139,464 KB
testcase_51	AC	562 ms 139,440 KB
testcase_52	AC	563 ms 139,460 KB
testcase_53	AC	567 ms 139,468 KB
testcase_54	AC	597 ms 139,448 KB
testcase_55	AC	644 ms 142,508 KB
testcase_56	AC	631 ms 143,936 KB
testcase_57	AC	618 ms 143,488 KB
testcase_58	AC	633 ms 142,696 KB
testcase_59	AC	617 ms 142,648 KB
testcase_60	AC	617 ms 143,188 KB
testcase_61	AC	621 ms 142,760 KB
testcase_62	AC	631 ms 143,040 KB
testcase_63	AC	613 ms 143,356 KB
testcase_64	AC	627 ms 143,868 KB
testcase_65	AC	188 ms 65,764 KB
testcase_66	AC	381 ms 139,032 KB
testcase_67	AC	267 ms 96,756 KB
testcase_68	AC	76 ms 11,792 KB
testcase_69	AC	104 ms 32,332 KB
testcase_70	AC	184 ms 59,588 KB
testcase_71	AC	111 ms 37,856 KB
testcase_72	AC	129 ms 42,748 KB
testcase_73	AC	174 ms 80,416 KB
testcase_74	AC	136 ms 39,676 KB
testcase_75	AC	615 ms 142,660 KB
testcase_76	AC	592 ms 142,508 KB
testcase_77	AC	589 ms 143,532 KB
testcase_78	AC	593 ms 143,712 KB
testcase_79	AC	605 ms 142,696 KB
testcase_80	AC	592 ms 144,092 KB
testcase_81	AC	590 ms 143,024 KB
testcase_82	AC	581 ms 142,892 KB
testcase_83	AC	591 ms 142,720 KB
testcase_84	AC	578 ms 142,572 KB
testcase_85	AC	2 ms 6,816 KB
testcase_86	AC	2 ms 6,824 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <algorithm>
#include <array>
#include <bit>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <concepts>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numbers>
#include <numeric>
#include <queue>
#include <random>
#include <ranges>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

constexpr int MOD{1'000'000'007};
constexpr int MOD2{998'244'353};
constexpr int INF{1'000'000'000}; //1e9
constexpr int NIL{-1};
constexpr long long LINF{1'000'000'000'000'000'000}; // 1e18
constexpr long double EPS{1E-10L};
using namespace std::literals;
namespace ranges = std::ranges;
namespace views = ranges::views;

template<class T, class S> bool chmax(T &a, const S &b){
    if(a < b){a = b; return true;}
    return false;
}
template<class T, class S> bool chmin(T &a, const S &b){
    if(b < a){a = b; return true;}
    return false;
}
template<class T> bool inside(T x, T lx, T rx){ //semi-open
    return (ranges::clamp(x, lx, rx-1) == x);
}
template<class T> bool inside(T x, T y, T lx, T rx, T ly, T ry){
    return inside(x, lx, rx) && inside(y, ly, ry);
}
template<class T, class S> std::istream &operator>>(std::istream &is, std::pair<T, S> &p){
    return is >> p.first >> p.second;
}
template<class T, class S> std::ostream &operator<<(std::ostream &os, const std::pair<T, S> &p){
    return os << p.first << " " << p.second;
}
template<class T> std::istream &operator>>(std::istream &is, std::vector<T> &v){
    {for(auto &e: v) is >> e;} return is;
}
template<class Container> void print_container(const Container &c, std::string sep = " "s, std::string end = "\n"s){
    for(int i{int(std::size(c))}; auto e: c) std::cout << e << (--i ? sep : end);
}
std::string yesno(bool x){return x ? "Yes"s : "No"s;}

std::vector<long long> primeFactor(long long n){
    std::vector<long long> vec;
    for(long long i{2}; i * i <= n; ++i) if(!(n % i)){
        vec.push_back(i);
        while(!(n % i)) n /= i;
    }
    if(n > 1) vec.push_back(n);
    return vec;
}

int main(){
    std::string S; std::cin >> S;
    int N{int(std::size(S))};
    auto primes{primeFactor(N)};
    int op_num{INF}; auto ans{S};
    for(auto p: primes){
        int a{int(N / p)}, op{};
        std::string s;
        std::vector cnts(a, std::vector<int>(26, 0));
        for(int i{}; i < N; ++i) ++cnts[i % a][S[i] - 'A'];
        for(int i{}; i < a; ++i){
            auto max_it{ranges::max_element(cnts[i])};
            op += p - *max_it;
            s += char('A' + int(std::distance(std::begin(cnts[i]), max_it)));
        }
        if(chmin(op_num, op)){
            ans = s;
            for(int i{1}; i < p; ++i) ans += s;
        }
    }
    std::cout << ans << std::endl;
    return 0;
}

yukicoder

結果

テストケース

ソースコード