문자열 패턴 변환 최소화

주어진 문자열에서 특정 패턴이 나타나지 않도록 비트 반전 작업을 수행하는 최소 횟수를 구하는 문제입니다. 타겟 패턴의 길이가 1, 2, 3 으로 제한되어 있어, 길이별로 경우를 나누어 접근해야 합니다.

패턴 길이가 1 일 때는 문자열에 해당 숫자가 아예 없어야 하므로 단순 반복 검사로 해결 가능합니다. 길이가 2 인 경우는 대칭성과 보수 연산 성질을 이용하여 대표적인 두 가지 경우인 '01'과 '11' 형태로 축소하여 분석합니다. '01' 형태는 앞쪽에서 뒤쪽으로 이동시키며 '1'이 연속되지 않게 만드는 로직이 필요하고, '11' 형태는 짝수 위치 조건을 만족하는지 확인합니다.

가장 복잡한 것은 길이가 3 인 경우입니다. 여기서는 '100', '101', '111' 형태의 무효화를 목표로 합니다. 특히 '111' 제거 시, 여분의 공간을 활용하여 한 번에 두 개를 제거할 수 있는지, 아니면 하나씩 분리해야 하는지에 대한 공간 계산이 핵심입니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

void solve_case_1(const string& src, const string& target) {
    char val = target[0];
    for (char c : src) {
        if (c == val) {
            cout << "-1\n";
            return;
        }
    }
    cout << "0\n";
}

void solve_case_2(const string& src, const string& target) {
    // Symmetry reduction handled before calling
    int n = src.size();
    if (target == "01") {
        int ops = 0, run = 0;
        for (int i = 0; i < n; ++i) {
            if (src[i] == '0') {
                if (run && i != run) ops++;
                run = 0;
            } else {
                run++;
            }
        }
        if (run && n != run) ops++;
        cout << ops << "\n";
    } else { // Target "11"
        int cnt = count(src.begin(), src.end(), '1');
        if (cnt > (n + 1) / 2) {
            cout << "-1\n";
            return;
        }
        int ans = 0;
        for (int i = 0; i < n - 1; ++i) {
            if (src[i] == '1' && src[i+1] == '1') ans++;
        }
        cout << ans << "\n";
    }
}

// ... (Similar restructuring for other cases would apply here, omitted for brevity in snippet)
// Full implementation requires normalizing inputs to canonical forms first.

void process() {
    int n; 
    cin >> n;
    string s, t;
    cin >> s >> t;
    
    // Normalization logic to map variations to canonical targets (e.g., 11, 01, 100, 101)
    // Implement checks based on length of t
    // Apply corresponding solver function
}

기하학적 구조 검증

평면 위에 주어진 선분들을 병합하여 특정 문자 모양 (THUPC 등) 을 이루는지 판별하는 문제입니다. 가로선과 세로선을 각각 분리한 후, 겹치는 구간을 합쳐주는 전처리 과정이 필요합니다. 최종적으로 형성된 선분이 정확히 7 개의 가로선과 8 개의 세로선으로 구성되어야 하며, 이들 간의 교차 관계가 정의된 구조를 만드는지 확인해야 합니다.

순서를 알 수 없으므로 가능한 모든 순열을 시도해 보는 방식이 기본적이지만, 전체 복잡도가 매우 높습니다. 따라서 동일한 x 좌표 또는 y 좌표를 가진 선분들 간의 우선순위 정렬을 통해 검색 공간을 줄이는 최적화가 필요합니다. 교차점의 유무를 세밀하게 체크하며 유효성을 판단합니다.

#include <iostream>
#include <vector>
#include <algorithm>

struct Horizontal { int y, l, r; };
struct Vertical { int x, d, u; };

bool merge_lines(vector<Horizontal>& h, vector<Vertical>& v) {
    sort(h.begin(), h.end(), [](const auto& a, const auto& b){
        return a.y != b.y ? a.y < b.y : a.l < b.l;
    });
    // Merge overlapping segments on same Y
    // Repeat similarly for Vertical lines
    
    return h.size() == 7 && v.size() == 8;
}

bool verify_topology(const vector<Horizontal>& h, const vector<Vertical>& v) {
    // Check intersection points strictly match expected graph topology
    // Loop permutations if necessary with pruning
    return true; 
}

int main() {
    int n; cin >> n;
    vector<Horizontal> hor;
    vector<Vertical> ver;
    // Read input and populate vectors
    // Sort and Merge
    // Call verify_topology
    // Output Yes/No
}

단조성 제약条件下的 동적 계획법

주어진 비교 연산자 사이클 (>, <, =) 를 만족하는 부분 수열의 최장 길이를 찾는 문제입니다. 일반적인 DP 의 상태는 $f_{i,j}$ (i 번째 원소까지, 현재 j 번째 관계 적용) 으로 설정될 수 있지만, 메모리 제한 (MLE) 을 피하기 위해 상태를 압축해야 합니다.

D P 최적화의 핵심은 그리디 성질에 있습니다. 실제 구현에서는 값의 범위를 기준으로 분할統治나 트리를 사용할 수 있으나, 효율성을 위해 누적 정보 구조인 Fenwick Tree (Binary Indexed Tree) 를 도입합니다. 이를 통해 이전 단계의 정보를 $O(\log N)$ 시간에 조회 및 갱신하며, 최종 경로 복원을 위해 선택한 부모 지점을 저장합니다.

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 20005;
int bit[MAXN];
int update(int idx, int val) {
    for (; idx < MAXN; idx += idx & -idx)
        bit[idx] = max(bit[idx], val);
}
int query(int idx) {
    int res = 0;
    for (; idx > 0; idx -= idx & -idx)
        res = max(res, bit[idx]);
    return res;
}

int main() {
    int n, k; cin >> n >> k;
    vector<int> a(n + 1), op(k + 1);
    // Read inputs...
    
    vector<int> dp(n + 1);
    vector<int> parent(n + 1);
    // Initialize BITs for different relation types (Greater, Equal, Less)
    // Iterate through elements, calculate max depth
    // Backtrack using parent array to print sequence
}

조합론과 구간 이동 제약

배열 원소의 합이 임계값 $k$ 를 초과하면 상대 순서가 고정되는 성질을 이용하여, 이동 가능한 범위를 계산하는 문제입니다. 요소를 '무거운 (Heavy)'와 '가벼운 (Light)'两类로 분류합니다. 무거운 요소끼리는 절대 위치 변경이 불가능하지만, 가벼운 요소들은 일정 범위 내에서 재배열이 가능합니다.

이때 가벼운 요소들의 허용 위치 구간은 불교차 또는 포함 관계를 가집니다. 이를 활용하여 값을 내림차순으로 정렬하고, BIT 를 사용하여 각 구간 내에 이미 존재하는 요소의 개수를 셈으로서 배치 가능한 조합의 수를 산출합니다. 팩토리얼을 미리 계산하여 이항계수를 빠르게 구하는 것이 필수적입니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

long long factorial[300005];
long long modInverse(long long a, int m) { /* implementation */ }

void solve() {
    int n, k; cin >> n >> k;
    vector<int> a(n + 1);
    // Read data
    // Coordinate compression or sorting values
    
    // Calculate L and R boundaries for each element using BIT
    // Group elements by value and their allowed intervals
    
    long long combinations = 1;
    // Iterate groups, multiply by Combination formula
    // Handle modulo arithmetic carefully
}

구간 해시 기반의 동적 계획법

다음 등장할 값들에 의해 결정되는 구간 정보를 상태로 두고 비용을 최소화하는 문제입니다. 상태 공간이 지수적으로 증가할 수 있으므로, 실제로 영향을 미치는 구간 차이의 곱을 이용해 상태를 고유하게 매핑 (Hashing) 합니다.

현재 위치 $i$에서 미래 값들이 만들어내는 간격의 크기를 기반으로 상태 인덱스를 생성합니다. 이를 통해 같은 구조를 가진 상태를 묶어서 탐색할 수 있게 됩니다. 각 단계마다 다음 원자를 포함하거나 제외하는 두 가지 선택지를 고려하며, 비용과 경우의 수를 동시에 갱신합니다. 시간 복잡도는 수학적으로 상한선이 보장되는 형태로 설계됩니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> a(n + 1);
    // Read input
    
    // Precompute interval counts and weights for each starting position
    // Use map or vector to store (MinCost, CountOfWays) per state
    
    vector> dp_states; // [cost][count]
    // Initial state setup
    // Iterate through positions
    // Transitions based on next value's rank among remaining elements
    // Update cost accumulation
}