연산자 우선순위 (D - Operator Precedence)

길이가 \\(2n\\)인 수열 \\(a_{2n}\\)을 찾는 문제입니다. 조건은 다음과 같습니다: \\((a_1 × a_2)+(a_3 × a_4)+\ldots+(a_{2n-1} × a_{2n})=a_1×(a_2+a_3)×\ldots×(a_{2n-2}+a_{2n-1})×a_{2n}\\)

#include <iostream>
using namespace std;

int main() {
    int n, x = 1, y = 1;
    cin >> n;
    cout << x << " " << y << endl;
    for(int i = 2; i <= n; i++) {
        if(i % 2 == 0) {
            x += 1;
        } else {
            y += 1;
        }
        cout << x << " " << y << endl;
    }
    return 0;
}

뱀 이동 (G - Snake Move)

\\(n × m\\) 크기의 맵에서 길이가 \\(k\\)인 뱀의 최소 이동 횟수를 구하는 문제입니다.

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

const int MAXN = 1005;
const int INF = 1e9;

int dis[MAXN * MAXN], Dis[MAXN * MAXN];
bool vis[MAXN * MAXN];
vector> adj[MAXN * MAXN];

void Dijkstra(int start) {
    priority_queue, vector>, greater>> pq;
    pq.push({0, start});
    Dis[start] = 0;
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (Dis[v] > Dis[u] + w) {
                Dis[v] = Dis[u] + w;
                pq.push({Dis[v], v});
            }
        }
    }
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    int rt;
    for (int i = 1; i <= k; ++i) {
        int x, y;
        cin >> x >> y;
        int pos = (x - 1) * m + y;
        dis[pos] = i;
        if (i == 1) rt = pos;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            char s;
            cin >> s;
            if (s == '.') {
                for (int t = 0; t < 4; ++t) {
                    int tx = i + dx[t], ty = j + dy[t];
                    if (tx >= 0 && tx < n && ty >= 0 && ty < m && s != '#') {
                        adj[(i - 1) * m + j].push_back({(tx - 1) * m + ty, 1});
                    }
                }
            }
        }
    }
    memset(Dis, 0x3f, sizeof Dis);
    Dijkstra(rt);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (Dis[(i - 1) * m + j] != INF) {
                cout << Dis[(i - 1) * m + j] << " ";
            }
        }
        cout << "\n";
    }
    return 0;
}

설탕 달콤함 II (H - Sugar Sweet II)

\\(n\\)개의 사건 순서에서 각 사건의 기대값을 계산하는 문제입니다.

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

const int MOD = 1e9 + 7;

int fact[500005], infact[500005];

int qmi(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1LL * res * a % MOD;
        a = 1LL * a * a % MOD;
        b >>= 1;
    }
    return res;
}

void init() {
    fact[0] = infact[0] = 1;
    for (int i = 1; i <= 500000; ++i) {
        fact[i] = 1LL * fact[i - 1] * i % MOD;
        infact[i] = 1LL * infact[i - 1] * qmi(i, MOD - 2) % MOD;
    }
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n), w(n), ans(n);
    vector<bool> f(n, false);
    vector<int> rd(n, 0), dep(n, 0);
    vector g(n);

    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i], --b[i];
    for (int i = 0; i < n; ++i) cin >> w[i];

    for (int i = 0; i < n; ++i) {
        if (a[i] < a[b[i]]) {
            ans[i] = (a[i] + w[i]) % MOD;
            f[i] = true;
        } else if (a[i] >= a[b[i]] + w[b[i]]) {
            ans[i] = a[i];
        } else {
            g[i].push_back(b[i]);
            ++rd[b[i]];
        }
    }

    vector<int> tp;
    for (int i = 0; i < n; ++i) {
        if (!rd[i]) tp.push_back(i);
    }

    for (int i = 0; i < tp.size(); ++i) {
        int u = tp[i];
        for (int v : g[u]) {
            if (--rd[v] == 0) tp.push_back(v);
        }
    }

    for (int i = tp.size() - 1; i >= 0; --i) {
        int u = tp[i];
        for (int v : g[u]) {
            if (f[v]) {
                dep[u] = dep[v] + 1;
                ans[u] = (a[u] + 1LL * w[u] * fact[dep[u]] % MOD * infact[n - dep[u]] % MOD) % MOD;
                f[u] = true;
            }
        }
    }

    for (int i = 0; i < n; ++i) cout << ans[i] << " ";
    cout << "\n";
}

int main() {
    init();
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

신비한 나무 (J - Mysterious Tree)

나무가 체인 또는 클로버 형태일 때, 해당 구조를 결정하는 알고리즘입니다.

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

bool checkEdge(int x, int y, vector<int>& degree) {
    return degree[x] == 1 && degree[y] == 1;
}

int main() {
    int n;
    cin >> n;
    vector<int> degree(n + 1, 0);
    for (int i = 1; i <= n / 2 + 3; ++i) {
        int x, y;
        cin >> x >> y;
        degree[x]++;
        degree[y]++;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if (checkEdge(i, j, degree)) {
                cout << "Chain" << endl;
                return 0;
            }
        }
    }
    cout << "Clover" << endl;
    return 0;
}

V-다이어그램 (M - V-Diagram)

V-형태의 수열에서 연속된 부분 수열의 평균 값을 최대화하는 문제입니다.

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

double maxAverageSubarray(vector<int>& nums) {
    double maxAvg = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        double sum = nums[i];
        for (int j = i - 1; j >= 0; --j) {
            sum += nums[j];
            maxAvg = max(maxAvg, sum / (i - j + 1));
        }
    }
    return maxAvg;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    cout << maxAverageSubarray(nums) << endl;
    return 0;
}