본문 바로가기

전체 글

(114)
[CodeUp 4035] 커피전문점 커피전문점 1. 첫째 줄에 트리의 노드(후보지)의 개수를 나타내는 정수 n이 주어진다. (2≤n≤100,000) 후보지는 1부터 n까지의 번호로 구분된다. 2. 둘째 줄부터 n-1개의 줄에 각 줄마다 후보지 쌍을 나타내는 두 codeup.kr 코드업을 밀던 중에 흥미로운 문제를 발견해서 포스팅한다. 다른 분들과 풀이의 방향이 달라 시간은 조금 느리지만, 다행히 코드는 깔끔하다. ㅎ 더보기 정해는 Union-Find 와 bfs 를 요구하지만, 사실 lca 만으로 풀린다! 생각의 편의를 위해 트리의 루트를 A로 만들어주자. 최적지의 집합이 (A-B 경로) $\cup $ (A-C 경로) 라는 것은 어렵지 않게 짐작 가능하다. 따라서 최적지의 개수는 $dep[a]+dep[b]-dep[lca(a,b)]+1$ 로 ..
Educational Codeforces Round 112 (Div. 2) Dashboard - Educational Codeforces Round 112 (Rated for Div. 2) - Codeforces codeforces.com 잘 풀고 있다는 느낌이 드는데 점수가 생각보다 오르지 않는다 ㅠ Prob. A $6:15=8:20=10:25$ 이므로 무엇을 선택할지는 딱히 중요하지 않다. $6$이상 짝수는 모두 만들 수 있으니 $n
Codeforces Round #735 (Div. 2) Dashboard - Codeforces Round #735 (Div. 2) - Codeforces codeforces.com 무난한 라운드였는데 C에서 크게 말리는 바람에 퍼플 퍼포를 받았다. D를 먼저 잡았으면 어땠을까 하는 아쉬움이 남는다. Prob. A 구간이 길어서 좋을 게 없다. $a_{i}*a_{i+1}$ 만 검사해주면 된다. Prob. B 식에서 뭔가를 관찰하기는 어려워 보이고, 범위가 조금 수상하다. $a_{i}
Centroid Decomposition 트리에서 센트로이드를 잡고 분할 정복을 돌리는 테크닉. 5820번: 경주 첫째 줄에 N과 K가 주어진다. 둘째 줄부터 N-1개 줄에는 H[i][0], H[i][1], L[i]가 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ K ≤ 1,000,000) www.acmicpc.net #include using namespace std; typedef pair pii; const int N=2e5+1; const int K=1e6+1; const int INF=1e9; int n,k; int sz[N],use[N],chk[K]; vector ad[N]; vector tree; int get_size(int cur,int prv) { sz[cur]=1; for(auto [nxt,w] : ad[cur]){ if..
Codeforces Global Round 15 Dashboard - Codeforces Global Round 15 - Codeforces codeforces.com 코이와 날짜가 겹치긴 했지만, 글로벌 라운드를 거를 생각은 애초에 없었고 결과는 성공적이었다. 블루에 5달 넘게 서식하면서 퍼플이 멀게만 느껴졌었는데, 최근에 퍼플 퍼포를 내면서 점수가 조금씩 오르더니 기어코 오렌지 퍼포를 받으며 퍼플에 안착했다. 코이 망한 건 아쉽지만 코포로 마음이 어느 정도 달래진 것 같다. TMI 대회가 시작됐는데 사이트가 먹통이 된 건지 와이파이가 느린 건지 접속이 되질 않았다. 일단 침착하게 폰으로 핫스팟을 켜고 문제를 읽었지만, 문제가 쉬웠는지 솔브 수가 무지막지하게 올라갔다. 노트북 접속이 성공했을 때는 5분 정도가 지난 시점이었고, 이미 몇천 명이 B번으..