본문 바로가기

전체 글

 (74)
Codeforces Round #741 (Div. 2) 이 날 또 블루 퍼포먼스를 만들어내고 블루 코앞까지 다가갔다. 최근 4번 동안의 코포로 260점 가량 올라왔다. 그래도 아쉬운 점이 꽤 많았다. C를 한번에 맞췄다면 퍼플 퍼포먼스가 나왔을텐데..... C를 풀고 D1을 7분만에 풀었으니 충분히 가능했다. 아깝다 ... A. The Miracle and the Sleeper Tag : Math 풀이 모듈러한 값이 커지려면 풀이는 뻔하다. 시간복잡도 : \(O(1)\) 전체 코드 #include #define pb push_back #define fi first #define se second #define all(x) ((x).begin()), ((x).end()) #define compress(x) sort(all(x)),(x).erase(unique(..
Codeforces Round #739 (Div. 3) https://codeforces.com/contest/1560 Dashboard - Codeforces Round #739 (Div. 3) - Codeforces codeforces.com 쉬운 셋이었으나......F1을 보고 F2풀이를 바로 찾았으나..... 노트북이 멈춰버렸다...... 독을 사기엔 너무 비싸서 전력 공급이 안되는 허브에 어거지로 모니터 두대를 연결해서 썼던게 문제였다. 몇달간 문제가 없어서 그냥 썼건만, 하필 코포 중에 이게 터져버렸다........ F2 풀이 찾고 블루까지 바로가는 상상을 했는데 마음이 아프다... 데스크톱이나 독을 사야겠다... 꼭....이젠 더 미루지 않겠다. 그래도 끝나고 모두 업솔빙했으니 이거로 만족해야겠다. A. Dislikes or Threes Tag ..
Codeforces Round #738 (Div. 2) https://codeforces.com/contest/1559 Dashboard - Codeforces Round #738 (Div. 2) - Codeforces codeforces.com 바로 이전 라운드인 737에 이어 또 블루 퍼포먼스가 나왔다. 그덕에 민트를 달성하게 되었고 너무 행복했다. 그리고 내가 처음으로 모든 문제를 업솔빙한 div2 라운드이다. A. Mocha and Math Tag : Bitsmasks, Math 풀이 부분 수열중에 부분 수열의 모든 원소를 bitwise and 한 결과의 최소를 구하는 문제인데, and를 하면 작아지면 작아지지 커지는 경우는 없기 때문에 모든 원소를 bitwise and 해주면된다. 시간복잡도 : \(O(N)\) 전체 코드 #include #defin..
[BOJ 16182] Dumae https://www.acmicpc.net/problem/16182 16182번: Dumae The first line contains two space-separated integers $N, M$. ($1 \leq N \leq 300,000,\ 0 \leq M \leq 1,000,000$) In the next $N$ lines, two space-separated integers $L_i,\ R_i$ are given. ($1 \leq L_i \leq R_i \leq N$) In the next $M$ lines, two space-sepa www.acmicpc.net Tag : Topological Sort, Greedy, Path Compression 문제 요약 위상정렬 순서에 어긋나지 않게 자..
AtCoder Beginner Contest 214 https://atcoder.jp/contests/abc214 Tasks - AtCoder Beginner Contest 214 AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 내 고질적인 문제인 구현이 또 발목을 잡았다. rmq 다이나믹 세그먼트 트리를 잘못구현해서 한시간반동안 손가락만 빨았다 A. New Generation ABC Tag : casework 풀이 하라는대로 하면 된다. 전체코드 #include #define endl '\n' #define fi first #define se second #define ..
[BOJ 17469] 트리의 색깔과 쿼리 https://www.acmicpc.net/problem/17469 17469번: 트리의 색깔과 쿼리 N개의 정점으로 구성된 트리가 있다. 각 정점은 1번부터 N번까지 번호가 매겨져있고, 1 이상 10만 이하의 자연수로 표현되는 색깔을 하나 갖고 있다. 루트는 1번 정점이고, 트리이기 때문에 임의 www.acmicpc.net Tag : Offline Query, DSU, Small To Large 풀이 간선을 제거하는 것은 일단 생각하지 말자. 어떠한 정점 \(A\)에서 갈 수 있는 점은 같은 컴포넌트에 있는 모든 정점이다. 컴포넌트들에 대해 서로 다른 색의 개수를 구하려면 일단 컴포넌트마다 \(std::set\)을 가지고 있어야할 듯하다. 이 때 컴포넌트는 \(DSU\)로 처리하면 되니 2번쿼리를 \(..
[BOJ 2261] 가장 가까운 두 점 https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net Tag : Sweeping 풀이 \(N^2\)개의 점 중에 가장 가까운 두 점을 구해야하는 문제인데 \(\binom{N}{2}\)의 경우를 모두 따져보기엔 \(N\)이 굉장히 크다. 적어도 \(O(N\sqrt{N})\), 되도록 \(O(NlogN)\)까지 만들면 좋을 듯하다. 일단 \(N\)개의 점을 \(X\)기준으로 정렬해보자. 정렬한 후 모든 점을 순회하며 \(..
[BOJ 2682] 최대 사이클 1 https://www.acmicpc.net/problem/2682 2682번: 최대 사이클 1 P는 1부터 n까지 수로 이루어진 순열이다. 최대 사이클 1은 P(1), P(P(1)), P(P(P(1))), ... 중 최댓값이다. 예를 들어 수열 P가 (3, 2, 5, 4, 1, 7, 8, 6) 이라면 P(1) = 3 P(P(1)) = P(3) = 5 P(P(P(1))) = P(5) = 1 따라서 3, 5, www.acmicpc.net Tag : Combinatorics 풀이 순열 \(P\)는 \( 1 N >> K; ll ans = 0; for(ll sz = 2; sz

티스토리툴바