시도 횟수: 2회

해결한 시간: 00:56

문제 번역(GPT)

핵심 아이디어

<aside> 💡

$n$의 약수인 $d$만 보면서 $n/d$만큼 반복 가능한지 확인 한다.

하모닉 시퀀스에 의해 시간 복잡도는 $O(N\log N)$에 수렴한다.

반복되는 문자열 $t$의 $i$번째 문자 $t_i$가 어떤 알파벳으로 가능할 지 검사한다.

</aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

int n, k;
string s[50'001];
bool ext[50'001][27];

void solve()
{
    cin >> n >> k;
    for(int i = 0; i<n; i++){
        memset(ext[i], false, sizeof(ext[i]));
    }
    for(int i = 0; i<k; i++){
        cin >> s[i];
    }

    for(int i = 0; i<k; i++){
        for(int j = 0; j<n; j++){
            ext[j][s[i][j]-'a'] = true;
        }
    }

    int ans = n;
    vector<char> o(n);
    for(int d = 1; d<=n; d++){
        if(n%d) continue;
        bool tot = true;

        for(int s = 0; s<d; s++){
            bool curS = false;

            for(int a = 0; a<26; a++){
                bool curA = true;
                
                for(int i = s; i<n; i+=d){
                    if(!ext[i][a]){
                        curA = false;
                        break;
                    }
                }

                if(curA){
                    curS = true;
                    o[s] = 'a'+a;
                    break;
                }
            }

            if(!curS){
                tot = false;
                break;
            }
        }

        if(tot){
            ans = d;
            break;
        }
    }

    for(int r = 0; r<n/ans; r++){
        for(int i = 0; i<ans; i++){
            cout << o[i];
        }
    }
    cout << "\\n";
}

signed main()
{
    FASTIO;
    int _tc; cin >> _tc;
    while (_tc--) solve();
    return 0;
}

복기

구현이 어려웠는데 그래도 잘 구현했다.