T1 다채로운 색상

문제는 다음과 같습니다:

• nxm 크기의 행렬이 주어집니다.
• (i,j) 위치에는 색깔 ci,j가 있습니다.
• 네 모서리의 색상이 모두 동일하지 않은 모든 하위 행렬의 수를 구하세요.

시간 복잡도 O(n²m)으로 해결할 수 있습니다. 두 행을 선택한 뒤 열을 스캔하면서 해당 열의 값들이 같으면 답에 기여할 가능성이 있습니다. 이를 위해 카운트 배열을 사용하여 현재 등장 횟수를 추적합니다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> grid(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> grid[i][j];
        }
    }

    long long total = 0;
    vector<long long> freq(1000001, 0);

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            fill(freq.begin(), freq.end(), 0); // Reset frequency
            for (int k = 1; k <= m; ++k) {
                if (grid[i][k] == grid[j][k]) {
                    total += freq[grid[i][k]];
                    freq[grid[i][k]]++;
                }
            }
        }
    }

    cout << (long long)n * m * (n + 1) * (m + 1) / 4 - total;
}

T2 피크 타임 여행

문제 요약은 다음과 같습니다:

• n개의 정점과 완전 그래프가 주어집니다.
• 각 시간 t에서 특정 정점들만 방문할 수 있습니다.
• S부터 T까지 가능한 경로 수를 계산하세요.

각 시간마다 유효한 정점의 개수를 곱하는 방식으로 해결할 수 있습니다. 이때 연속된 구간에서는 동일한 값을 가지므로, 효율적으로 계산하기 위해 스캐닝 및 지수 함수를 활용합니다.

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

using namespace std;

const int MOD = 1e9 + 7;

int power(int base, int exp) {
    int res = 1;
    while (exp > 0) {
        if (exp % 2 == 1) res = (long long)res * base % MOD;
        base = (long long)base * base % MOD;
        exp /= 2;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, S, T;
    cin >> n >> m >> S >> T;

    struct Event { int time, delta; };
    vector<Event> events;

    for (int i = 0; i < m; ++i) {
        int x, l, r;
        cin >> x >> l >> r;
        events.push_back({l, -1});
        events.push_back({r + 1, 1});
    }

    events.push_back({S, 0});
    events.push_back({T + 1, 0});

    sort(events.begin(), events.end(), [](const Event &a, const Event &b) { return a.time < b.time; });

    int current = n;
    long long result = 1;
    for (size_t i = 1; i < events.size(); ++i) {
        int duration = events[i].time - events[i - 1].time;
        if (duration > 0) {
            result = (result * power(current, duration)) % MOD;
        }
        current += events[i].delta;
    }

    cout << result;
}

T3 최적화된 세그먼트 트리

문제 설명은 다음과 같습니다:

• 길이 n의 세그먼트 트리를 구성합니다.
• q개의 쿼리에 대해 각 쿼리의 처리 비용을 최소화하세요.

구간 DP로 접근할 수 있습니다. 주요 아이디어는 특정 위치에서 나누었을 때 영향을 받는 쿼리들의 수를 사전에 계산하여 저장하는 것입니다.

#include <iostream>
#include <vector>

using namespace std;

const long long INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;

    vector<pair<int, int>> queries(q);
    for (auto &[l, r] : queries) cin >> l >> r;

    vector<int> w(n + 1, 0);
    vector<vector<int>> num(n + 1, vector<int>(n + 1, 0));

    for (auto &[l, r] : queries) {
        w[l]++;
        w[r]--;
        num[l][r]++;
    }

    for (int i = 1; i <= n; ++i) w[i] += w[i - 1];

    for (int len = 1; len <= n; ++len) {
        for (int l = 1, r = l + len - 1; r <= n; ++l, ++r) {
            num[l][r] += num[l - 1][r] + num[l][r + 1] - num[l - 1][r + 1];
        }
    }

    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, INF));

    for (int len = 1; len <= n; ++len) {
        for (int l = 1, r = l + len - 1; r <= n; ++l, ++r) {
            if (len == 1) {
                dp[l][r] = 0;
                continue;
            }
            for (int k = l; k < r; ++k) {
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + w[k] - num[l][r]);
            }
        }
    }

    cout << dp[1][n] + q;
}