대회 흐름 요약

• T1을 먼저 시작, 고민 후 즉시 해결. 대양에서 한 번에 통과.
• T2도 비슷한 방식으로 빠르게 해결. 역시 대양에서 통과.
• 15:48 T3에 접근, 그러나 잘못된 접근으로 실패. 다만 에 수를 차례로 추가한다. 선택 가능한 원소 최대 개수는, 어떤 두 수 사이의 차이가 1보다 작지 않도록 해야 한다.

  대회 당시: 어제 연습 문제에서 유사한 연속 구간 관리 문제를 풀어본 적이 있어, 이를 바로 적용.

  해결 전략: 동일한 값은 하나만 선택 가능하므로, 존재 여부만 저장하면 된다. 연속된 숫자 그룹은 서로 영향을 주지 않으며, 크기가 개 선택 가능.

  연속 구간을 유지하기 위해 union-find 자료구조를 사용. 새로운 수가 삽입될 때, 인접한 구간과 병합하면서 기존 선택 개수를 제거하고, 새 구간의 선택 수를 추가한다.

  시간 복잡도: #include <bits/stdc++.h> #define inf 0x3f3f3f3f #define infll 0x3f3f3f3f3f3f3f3fll using namespace std; int n; int val[300010]; bool exists[500010]; int parent[500010], size_[500010]; int find_root(int x) { return parent[x] == x ? x : parent[x] = find_root(parent[x]); } void merge_sets(int x, int y) { x = find_root(x); y = find_root(y); if (x == y) return; if (size_[x] > size_[y]) swap(x, y); parent[x] = y; size_[y] += size_[x]; } int max_val = 0; long long total_selected = 0; int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); freopen("set.in", "r", stdin); freopen("set.out", "w", stdout); cin >> n; for (int i = 1; i <= n; ++i) { cin >> val[i]; max_val = max(max_val, val[i]); } for (int i = 1; i <= max_val; ++i) { parent[i] = i; size_[i] = 1; } for (int i = 1; i <= n; ++i) { int x = val[i]; if (!exists[x]) { // 왼쪽 인접 구간 처리 if (x > 1 && exists[x - 1]) { int root_left = find_root(x - 1); total_selected -= (size_[root_left] + 1) / 2; merge_sets(x - 1, x); } // 오른쪽 인접 구간 처리 if (x < max_val && exists[x + 1]) { int root_right = find_root(x + 1); total_selected -= (size_[root_right] + 1) / 2; merge_sets(x + 1, x); } exists[x] = true; total_selected += (size_[find_root(x)] + 1) / 2; } cout << total_selected << " "; } cout << "\n"; return 0; }

  T2 – 도시 탐방 (최대 2회 이동)

  문제 요약: 개의 장애물이 존재. 시작 위치는

  여기서 중요한 아이디어는, "오른쪽 이동 이후 아래로 이동"이 가능한 영역은 열 기준으로 전파되는 성질이 있으며, 이를 트리 구조나 **트리 배열**(Fenwick Tree)로 효율적으로 관리할 수 있다. 스캔 라인 기법을 활용하여, 특정 열이 언제까지 유효한지를 추적.

  시간 복잡도: #include <bits/stdc++.h> #define inf 0x3f3f3f3f #define infll 0x3f3f3f3f3f3f3f3fll using namespace std; int n, m, k; struct Point { int r, c; bool operator<(const Point& other) const { return r == other.r ? c < other.c : r < other.r; } } obstacles[200010]; int row_max[200010]; // 각 행에서 도달 가능한 최대 열 int col_max[200010]; // 각 열에서 도달 가능한 최대 행 int first_row_limit = m; // (1,1)에서 오른쪽으로 이동 가능한 최대 열 int first_col_limit = n; // (1,1)에서 아래로 이동 가능한 최대 행 int bit[200010]; static inline int lowbit(int x) { return x & (-x); } void add(int pos, int delta) { while (pos <= m) { bit[pos] += delta; pos += lowbit(pos); } } int query(int pos) { int res = 0; while (pos) { res += bit[pos]; pos -= lowbit(pos); } return res; } vector<int> end_events[200010]; // 각 행에서 종료되는 열 리스트 int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); freopen("motor.in", "r", stdin); freopen("motor.out", "w", stdout); cin >> n >> m >> k; for (int i = 1; i <= k; ++i) { cin >> obstacles[i].r >> obstacles[i].c; } fill(row_max + 1, row_max + n + 1, m); fill(col_max + 1, col_max + m + 1, n); for (int i = 1; i <= k; ++i) { int r = obstacles[i].r, c = obstacles[i].c; row_max[r] = min(row_max[r], c - 1); col_max[c] = min(col_max[c], r - 1); if (r == 1) first_row_limit = min(first_row_limit, c - 1); if (c == 1) first_col_limit = min(first_col_limit, r - 1); } long long ans1 = 0, ans2 = 0; for (int j = 1; j <= first_row_limit; ++j) ans1 += col_max[j]; for (int i = 1; i <= first_col_limit; ++i) ans2 += row_max[i]; long long overlap = 0; for (int j = 1; j <= first_row_limit; ++j) { add(j, 1); if (col_max[j] != n) { end_events[col_max[j] + 1].push_back(j); } } for (int i = 1; i <= first_col_limit; ++i) { for (int ev : end_events[i]) add(ev, -1); overlap += query(row_max[i]); } cout << ans1 + ans2 - overlap << "\n"; return 0; }

  전반적인 평가

  • T1은 전형적인 입문 문제. 빠르게 해결.
  • T2는 포함-배제 원리에 대한 직관이 중요했으나, 구현이 다소 복잡함.
  • T3, T4는 부분 점수만 획득. 완전한 풀이는 불가능.
  • 대회 후 휴식 후, 마지막 순간에 T3의 핵심 관계를 예측하여 완전히 해결.
  • 30분 내 3문제를 완전히 해결.