A 문제: 최적 직사각형 둘레

문제의 핵심은 최종 도형의 둘레가 최대 너비와 높이를 가진 직사각형의 둘레와 같다는 결론을 도출하는 것입니다.

#include 
using namespace std;
typedef long long ll;

void solve() {
    int test_case;
    cin >> test_case;
    
    while (test_case--) {
        int shape_count;
        cin >> shape_count;
        
        ll max_width = 0, max_height = 0;
        for (int i = 0; i < shape_count; i++) {
            ll w, h;
            cin >> w >> h;
            max_width = max(max_width, w);
            max_height = max(max_height, h);
        }
        
        cout << 2 * (max_width + max_height) << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

B 문제: 스탈린 정렬 최소 삭제

스탈린 정렬은 비내림차순 수열을 생성합니다. 각 원소 a_i를 유지하려면 a_i 앞에 있는 모든 수가 a_i보다 작아야 하며, 뒤에 있는 모든 수도 a_i보다 작거나 같아야 합니다. O(n^2) 시간 복잡도로 각 원소에 대해 필요한 삭제 횟수를 계산합니다.

#include 
using namespace std;
typedef long long ll;

const int MAX_N = 2005;

void solve() {
    int test_case;
    cin >> test_case;
    
    while (test_case--) {
        int n;
        cin >> n;
        
        vector<int> arr(MAX_N);
        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
        }
        
        int min_deletions = n;
        for (int i = 1; i <= n; i++) {
            int deletions = i - 1;
            for (int j = i + 1; j <= n; j++) {
                if (arr[j] > arr[i]) {
                    deletions++;
                }
            }
            min_deletions = min(min_deletions, deletions);
        }
        
        cout << min_deletions << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

C 문제: 조건 변환과 DFS 탐색

문제의 조건을 변환하면, 1 ≤ i ≤ n일 때 a_i + i - 1 = |a|인 경우 크기를 a_i + i - 1 + i - 1로 조정해야 합니다. DFS를 사용하고 map으로 방문 여부를 표시하여 각 값이 최대 한 번만 탐색되도록 O(n) 시간 복잡도로 해결합니다.

#include 
using namespace std;
typedef long long ll;
typedef pair PLI;

const int MAX_N = 300005;

void solve() {
    int test_case;
    cin >> test_case;
    
    while (test_case--) {
        int n;
        cin >> n;
        
        vector<ll> a(MAX_N);
        vector<PLI> elements(MAX_N);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            elements[i] = {a[i] + i - 1, i - 1};
        }
        
        sort(elements.begin() + 1, elements.begin() + n + 1);
        
        map visited;
        ll result = n;
        
        function dfs = [&](ll size) {
            if (visited.count(size)) return;
            visited[size] = true;
            result = max(result, size);
            
            if (size > elements[n].first) return;
            
            PLI temp = {size, 0};
            int left = lower_bound(elements.begin() + 1, elements.begin() + n + 1, temp) - elements.begin();
            
            temp.second = n;
            int right = upper_bound(elements.begin() + 1, elements.begin() + n + 1, temp) - elements.begin() - 1;
            
            for (int i = left; i <= right; i++) {
                if (elements[i].second == 0) continue;
                dfs(size + elements[i].second);
            }
        };
        
        dfs(n);
        cout << result << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

D1 문제: 동적 프로그래밍 접근

주어진 데이터 범위 nm ≤ 3e5에서 O(nm) 해법이 필요함을 관찰할 수 있습니다. DP를 사용하여 f[i][j]를 k 값이 i일 때 a에 남은 첫 번째 원소의 인덱스가 j인 최소 비용으로 정의합니다.

#include 
using namespace std;
typedef long long ll;

const int MAX_N = 300005;
const ll INF = 1e18;

void solve() {
    int test_case;
    cin >> test_case;
    
    while (test_case--) {
        int n, m;
        cin >> n >> m;
        
        vector<ll> prefix_sum(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> prefix_sum[i];
            prefix_sum[i] += prefix_sum[i - 1];
        }
        
        vector<ll> b(m + 1);
        for (int i = 1; i <= m; i++) {
            cin >> b[i];
        }
        
        vector dp(2, vector<ll>(n + 2, INF));
        dp[1][1] = 0;
        ll answer = INF;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n + 1; j++) {
                dp[(i + 1) & 1][j] = INF;
            }
            
            for (int j = 1; j <= n; j++) {
                int k = upper_bound(prefix_sum.begin() + j, prefix_sum.begin() + n + 1, 
                                   b[i] + prefix_sum[j - 1]) - prefix_sum.begin();
                
                if (k > j) {
                    dp[i & 1][k] = min(dp[i & 1][k], dp[i & 1][j] + m - i);
                }
                
                dp[(i + 1) & 1][j] = min(dp[(i + 1) & 1][j], dp[i & 1][j]);
            }
            
            answer = min(answer, dp[i & 1][n + 1]);
        }
        
        cout << (answer == INF ? -1 : answer) << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}