전반적으로 난이도가 낮았으나, 특정 문제에서는 접근 방식의 세부적 오류가 성능 저하를 유발할 수 있었다. 특히 E 문제와 같이 이분 탐색을 활용할 때는 범위의 정확한 설정이 중요했으며, F 문제에서는 초기 입력 해석의 부주의가 문제를 복잡하게 만들었다. 이하에서는 각 문제별로 효율적인 구현 방식을 검토하고 최적화 코드를 제시한다.

문제 D: 구간 연결성 최적화

이 문제의 핵심은 정렬된 데이터 위에서 인접 요소 간의 차이를 제한하는 가장 긴 연속된 부분 배열을 찾는 것이다. 배열을 정렬 후, 슬라이딩 윈도우 혹은 투포인터 기법을 적용하여 조건 (차이 <= K) 을 만족하는 최대 구간 길이를 산출한다. 구해진 길이만큼 유지 가능한 데이터를 제외하고 나머지를 제거하는 형태로 결과가 도출된다.

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

using namespace std;
using ll = long long;

const int MAX_N = 200005;
int nums[MAX_N];

void processTestCase() {
    int n, limit;
    cin >> n >> limit;
    
    for(int i = 1; i <= n; ++i) {
        cin >> nums[i];
    }

    if (n == 1) {
        cout << 0 << "\n";
        return;
    }

    sort(nums + 1, nums + n + 1);

    int maxStreakLen = 0;
    int left = 1;
    
    for(int right = 2; right <= n; ) {
        int currentStart = right;
        int tempLen = 0;
        int ptr = right;
        
        while(ptr <= n && (nums[ptr] - nums[ptr - 1]) <= limit) {
            tempLen++;
            ptr++;
        }
        
        if(tempLen > maxStreakLen) {
            maxStreakLen = tempLen;
        }
        right = ptr;
    }

    cout << n - maxStreakLen - 1 << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) {
        processTestCase();
    }
    return 0;
}

문제 E: 목적지 도달을 위한 최소 변수 탐색

목표 값 C 에 도달하기 위해 필요한 입력값들의 조정 크기 X 를 최소화하는 문제다. X 값을 후보로 잡고 모든 입력값에 대해 (원래값 + 2X)^2 을 누적하여 C 이상인지 확인하는 체크 함수(check) 를 구성한다. 이를 바탕으로 범위를 이분 검색함으로써 정답을 도출할 수 있다. 상한선은 충분히 큰 값으로 설정하여 누락 방지한다.

#include <iostream>
#include <cmath>

using namespace std;
using ll = long long;

const int MAX_N = 200005;
int baseValues[MAX_N];
int nCount;
ll targetSumLimit;

bool isValidConfigration(ll adjustX) {
    ll totalSqSum = 0;
    for(int i = 1; i <= nCount; ++i) {
        ll val = baseValues[i] + 2 * adjustX;
        totalSqSum += val * val;
        if(totalSqSum >= targetSumLimit) return true;
    }
    return false;
}

void solveProblemE() {
    cin >> nCount >> targetSumLimit;
    for(int i = 1; i <= nCount; ++i) {
        cin >> baseValues[i];
    }

    ll lowerBound = 0, upperBound = 1000000000;
    ll optimalAns = upperBound;

    while(lowerBound <= upperBound) {
        ll mid = lowerBound + (upperBound - lowerBound) / 2;
        if(isValidConfigration(mid)) {
            optimalAns = mid;
            upperBound = mid - 1;
        } else {
            lowerBound = mid + 1;
        }
    }
    cout << optimalAns << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) {
        solveProblemE();
    }
    return 0;
}

문제 F: 조화급수 기반 계층 구조 분석

주어진 숫자들의 빈도 정보를 바탕으로 각 위치의 누적 값을 계산하는 문제다. 모든 배수를 직접 탐색하면 O(N^2) 이 되므로,调和级수 (Harmonic Series) 의 성질인 O(N log N) 을 활용해야 한다. 먼저 각 숫자의 등장 횟수를 기록하고, 이후 그 숫자가 포함되는 모든 배수에 대해 분배량을 더해준다. 최종적으로 최대 빈도를 가진 위치를 출력한다.

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

using namespace std;

const int MAX_VAL = 200005;
int freqMap[MAX_VAL];
int contribution[MAX_VAL];

void runLogicF() {
    int nVal;
    cin >> nVal;
    
    // Reset arrays
    memset(freqMap, 0, sizeof(freqMap));
    memset(contribution, 0, sizeof(contribution));

    for(int i = 1; i <= nVal; ++i) {
        int inputNum;
        cin >> inputNum;
        if(inputNum <= nVal) {
            freqMap[inputNum]++;
        }
    }

    // Propagate contributions using harmonic logic
    for(int i = 1; i <= nVal; ++i) {
        if(freqMap[i] > 0) {
            for(int multiple = i; multiple <= nVal; multiple += i) {
                contribution[multiple] += freqMap[i];
            }
        }
    }

    sort(contribution + 1, contribution + nVal + 1);
    cout << contribution[nVal] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tCases;
    cin >> tCases;
    while(tCases--) {
        runLogicF();
    }
    return 0;
}

문제 G: 기하학적 좌표 변환 및 조합

점들을 이어 직선의 방향성을 판별하는 문제로, x+y 와 x-y 를 이용하여 대각선 축을 관리하는 것이 핵심이다. 또한 x축과 y축에 평행한 라인들도 고려해야 한다. map 자료구조를 활용하여 각 좌표 변환 값마다 점이 몇 개인지 세고, k 개의 점을 지나는 직선이 있을 때 만들 수 있는 선분 수는 k*(k-1) 이므로 이를 모두 합산한다. 결과값 계산 시 장수형을 주의하여 처리한다.

#include <iostream>
#include <map>
#include <vector>

using namespace std;
using ll = long long;

struct Point {
    ll x, y;
};

void executeG() {
    int pCount;
    cin >> pCount;
    
    map<ll, int> diagSumMap; // x+y
    map<ll, int> diagDiffMap; // x-y
    map<ll, int> colMap;       // x-axis
    map<ll, int> rowMap;       // y-axis
    
    vector<Point> points(pCount + 1);
    
    for(int i = 1; i <= pCount; ++i) {
        cin >> points[i].x >> points[i].y;
        diagSumMap[points[i].x + points[i].y]++;
        diagDiffMap[points[i].y - points[i].x]++;
        colMap[points[i].x]++;
        rowMap[points[i].y]++;
    }

    ll totalPairs = 0;

    auto calculateCombinations = [&](auto& mp) {
        for(auto const& [key, val] : mp) {
            if(val > 1) {
                totalPairs += (ll)val * (val - 1);
            }
        }
    };

    calculateCombinations(diagSumMap);
    calculateCombinations(diagDiffMap);
    calculateCombinations(colMap);
    calculateCombinations(rowMap);

    cout << totalPairs << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int testCnt;
    cin >> testCnt;
    while(testCnt--) {
        executeG();
    }
    return 0;
}