이번 라운드의 A~G번 문제에 대한 핵심 아이디어와 구현 방법을 정리합니다.

A. Don't Try to Count

문자열 t가 s의 연속 부분문자열이 되도록 만드는 문제입니다. s를 반복하여 이어붙이면 길이가 2배로 늘어나는 특성을 활용합니다. n·m ≤ 25 조건 덕분에 최대 5번만 반복하면 충분합니다.

#include <bits/stdc++.h>
using namespace std;

bool isSubstr(const string& text, const string& pat) {
    if (pat.empty()) return true;
    for (size_t i = 0; i + pat.length() <= text.length(); ++i) {
        if (text.substr(i, pat.length()) == pat) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tc;
    cin >> tc;
    while (tc--) {
        int n, m;
        string base, target;
        cin >> n >> m >> base >> target;
        
        int res = -1;
        for (int step = 0; step <= 5; ++step) {
            if (isSubstr(base, target)) {
                res = step;
                break;
            }
            base += base;
        }
        cout << res << "\n";
    }
    return 0;
}

B. Three Threadlets

세 개의 실을 잘라 길이가 같은 조각들로 만드는 문제입니다. 잘라야 하는 횟수가 6번 이하여야 하므로, 가능한 조각 개수(3, 4, 5, 6) 각각에 대해 검증합니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool valid(ll a, ll b, ll c, ll pieces) {
    ll total = a + b + c;
    if (total % pieces != 0) return false;
    ll unit = total / pieces;
    if (a % unit || b % unit || c % unit) return false;
    ll cuts = a/unit + b/unit + c/unit - 3;
    return cuts <= 3;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tc;
    cin >> tc;
    while (tc--) {
        ll x, y, z;
        cin >> x >> y >> z;
        bool ok = valid(x,y,z,3) || valid(x,y,z,4) || valid(x,y,z,5) || valid(x,y,z,6);
        cout << (ok ? "YES" : "NO") << "\n";
    }
    return 0;
}

C. Perfect Square

행렬을 회전시켜 완전 제곱수 형태로 만드는 문제입니다. 중심을 기준으로 4개 대칭 위치를 묶어 각 위치의 최대값으로 통일시키는 비용을 계산합니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tc;
    cin >> tc;
    while (tc--) {
        int n;
        cin >> n;
        vector<string> g(n);
        for (auto& row : g) cin >> row;
        
        int cost = 0;
        int half = n / 2;
        for (int i = 0; i < half; ++i) {
            for (int j = 0; j < half; ++j) {
                int a = g[i][j] - '0';
                int b = g[j][n-1-i] - '0';
                int c = g[n-1-j][i] - '0';
                int d = g[n-1-i][n-1-j] - '0';
                int mx = max({a, b, c, d});
                cost += (mx - a) + (mx - b) + (mx - c) + (mx - d);
            }
        }
        cout << cost << "\n";
    }
    return 0;
}

D. Divide and Equalize

연산 과정에서 전체 곱이 불변임을 이용합니다. 각 수를 소인수분해하여 모든 소인수의 총 개수가 n으로 나누어떨어지는지 확인합니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tc;
    cin >> tc;
    while (tc--) {
        int n;
        cin >> n;
        unordered_map<int, int> freq;
        
        for (int i = 0; i < n; ++i) {
            long long v;
            cin >> v;
            for (long long p = 2; p * p <= v; ++p) {
                while (v % p == 0) {
                    freq[p]++;
                    v /= p;
                }
            }
            if (v > 1) freq[v]++;
        }
        
        bool ok = true;
        for (auto& [p, c] : freq) {
            if (c % n != 0) { ok = false; break; }
        }
        cout << (ok ? "YES" : "NO") << "\n";
    }
    return 0;
}

E. Block Sequence

위치 i에서 i + a[i]로 점프하는 구조를 역순으로 동적 계획법으로 처리합니다. dp[i]를 i번째부터 끝까지 고려했을 때의 최소 삭제 횟수로 정의합니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tc;
    cin >> tc;
    while (tc--) {
        int n;
        cin >> n;
        vector<int> a(n + 2), dp(n + 3, 0);
        for (int i = 1; i <= n; ++i) cin >> a[i];
        
        dp[n + 1] = 0;
        for (int i = n; i >= 1; --i) {
            int nxt = i + a[i] + 1;
            int keep = (nxt <= n + 1) ? dp[nxt] : n + 1;
            dp[i] = min(dp[i + 1] + 1, keep);
        }
        cout << dp[1] << "\n";
    }
    return 0;
}

F. Minimum Maximum Distance

트리 위에서 각 정점까지의 최대 거리를 최소화하는 문제입니다. 실제로는 임의의 표记된 정점에서 BFS를 두 번 수행하여 지름을 구하면 해결됩니다.

지름 길이를 d라 할 때, 답은 ⌈d / 2⌉입니다.

G. Anya and the Mysterious String

구간 내에 회문이 존재하는지 판별하는 문제입니다. 길이 2 또는 3인 회문만 검사하면 충분하며, 펜윅 트리로 구간 회전을 처리하고 set으로 회문 위치를 관리합니다.

#include <bits/stdc++.h>
using namespace std;

struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick(int n = 0) { init(n); }
    void init(int n_) {
        n = n_;
        bit.assign(n + 2, 0);
    }
    void add(int idx, int val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] = (bit[idx] + val) % 26;
    }
    int sum(int idx) {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx) res = (res + bit[idx]) % 26;
        return (res % 26 + 26) % 26;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tc;
    cin >> tc;
    while (tc--) {
        int n, q;
        cin >> n >> q;
        string str;
        cin >> str;
        
        Fenwick fw(n);
        for (int i = 1; i <= n; ++i) {
            fw.add(i, (str[i-1] - 'a') - fw.sum(i-1));
        }
        
        set<int> len2, len3;
        auto refresh = [&](int pos) {
            if (pos < 1 || pos > n) return;
            if (pos < n) {
                if (fw.sum(pos) == fw.sum(pos + 1)) len2.insert(pos);
                else len2.erase(pos);
            }
            if (pos < n - 1) {
                if (fw.sum(pos) == fw.sum(pos + 2)) len3.insert(pos);
                else len3.erase(pos);
            }
        };
        
        for (int i = 1; i < n; ++i) refresh(i);
        
        while (q--) {
            int type;
            cin >> type;
            if (type == 1) {
                int l, r, k;
                cin >> l >> r >> k;
                k = (k % 26 + 26) % 26;
                fw.add(l, k); fw.add(r + 1, -k);
                for (int d = -2; d <= 2; ++d) refresh(l + d);
                for (int d = -2; d <= 2; ++d) refresh(r + d);
            } else {
                int l, r;
                cin >> l >> r;
                bool bad = false;
                auto it2 = len2.lower_bound(l);
                if (it2 != len2.end() && *it2 <= r - 1) bad = true;
                auto it3 = len3.lower_bound(l);
                if (it3 != len3.end() && *it3 <= r - 2) bad = true;
                cout << (bad ? "NO" : "YES") << "\n";
            }
        }
    }
    return 0;
}