본문 바로가기

분류 전체보기

(74)
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 ThreesTag : Brute Force 풀이조금 생각해보면 \(K=1000\)일 때 \(10000\)정도에 가까이 있겠다라고 생각해서 ..
Codeforces Round #738 (Div. 2) https://codeforces.com/contest/1559 Dashboard - Codeforces Round #738 (Div. 2) - Codeforces codeforces.com바로 이전 라운드인 737에 이어 또 블루 퍼포먼스가 나왔다. 그덕에 민트를 달성하게 되었고 너무 행복하다. 그리고 내가 처음으로 모든 문제를 업솔빙한 div2 라운드이다.A. Mocha and MathTag : Bitsmasks, Math 풀이부분 수열중에 부분 수열의 모든 원소를 bitwise and 한 결과의 최소를 구하는 문제인데, and를 하면 작아지면 작아지지 커지는 경우는 없기 때문에 모든 원소를 bitwise and 해주면된다. 시간복잡도 : \(O(N)\) 전체 코드#include #define end..
[BOJ 16182] Dumae https://www.acmicpc.net/problem/16182 16182번: DumaeThe 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-sepawww.acmicpc.netTag : Topological Sort, Greedy, Path Compression 문제 요약위상정렬 순서에 어긋나지 않게 자리를 배..
AtCoder Beginner Contest 214 https://atcoder.jp/contests/abc214 Tasks - AtCoder Beginner Contest 214AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jprmq 다이나믹 세그먼트 트리를 잘못구현해서 한시간반동안 디버깅했다.A. New Generation ABCTag : casework 풀이하라는대로 하면 된다. 전체코드#include #define endl '\n'#define fi first#define se second#define all(x) ((x).begin()),((x).end())#defin..
[BOJ 17469] 트리의 색깔과 쿼리 https://www.acmicpc.net/problem/17469 17469번: 트리의 색깔과 쿼리N개의 정점으로 구성된 트리가 있다. 각 정점은 1번부터 N번까지 번호가 매겨져있고, 1 이상 10만 이하의 자연수로 표현되는 색깔을 하나 갖고 있다. 루트는 1번 정점이고, 트리이기 때문에 임의www.acmicpc.netTag : Offline Query, DSU, Small To Large 풀이간선을 제거하는 것은 일단 생각하지 말자. 어떠한 정점 \(A\)에서 갈 수 있는 점은 같은 컴포넌트에 있는 모든 정점이다. 컴포넌트들에 대해 서로 다른 색의 개수를 구하려면 일단 컴포넌트마다 std::set을 가지고 있어야할 듯하다.이 때 컴포넌트는 DSU로 처리하면 되니 2번쿼리를 std::set::size를..
[BOJ 2261] 가장 가까운 두 점 https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도www.acmicpc.netTag : Sweeping 풀이\(N^2\)개의 점 중에 가장 가까운 두 점을 구해야하는 문제인데 \(\binom{N}{2}\)의 경우를 모두 따져보기엔 \(N\)이 굉장히 크다. 적어도 \(O(N\sqrt{N})\), 되도록 \(O(NlogN)\)까지 만들면 좋을 듯하다. 일단 \(N\)개의 점을 \(X\)기준으로 정렬해보자. 정렬한 후 모든 점을 순회하며 \(std:..
[BOJ 2682] 최대 사이클 1 https://www.acmicpc.net/problem/2682 2682번: 최대 사이클 1P는 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.netTag : Combinatorics 풀이순열 \(P\)는 \( 1 \( P_{P_{1}} \)....를 반복해1로 돌아오는 사이클 안에서 가장 큰 수를 구하는 문제이다. 일단 문제 이름부터 사이클이니 그래프로 해석해봐야 할 듯한 느낌이 강하게 든다. 그러기 위해서 일단 \(1P_..
Codeforces Round #737 (Div. 2) https://codeforces.com/contest/1557 Dashboard - Codeforces Round #737 (Div. 2) - Codeforces codeforces.com최종적인 퍼포먼스는 1639점으로 나쁘지 않게 나왔지만대회중 판단에 아쉬운 점이 꽤 있었다.A. Ezzat and Two subsequencesTag : sort, prefix sum 풀이작은건 작은거끼리, 큰건 큰거끼리 합쳐주는게 평균에 이득이라 생각했다. 두 그룹을 가르는 기준선을 순회하며 모든 기준선에 대해 계산을 수행하면 답을 얻을 수 있다. 나는 딱 보자마자 이것을 생각해내지 못해서 20분을 날렸고long double로 입력을 받아서 첫 제출은 TLE, 두번째 제출은 아슬아슬하게 980ms로 통과했다. 아마 ..