본문 바로가기

전체 글

(158)
Harbour.Space bla bla (Div. 1 + Div. 2) Dashboard - Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2) - Codeforces codeforces.com 참가하는 라운드를 모두 포스팅하자고 다짐했는데 어째 잘한 라운드만 올리는 것 같다. B, D번 시스텟이 터지지만 않는다면 아마 순위도 더 오르고 맥레도 갱신할 수 있을 것 같다. 계속 퍼포먼스가 2000 아래에 찍혀서 조금 아쉽긴 한데, 꾸준히 나오는 실수만 줄이면 곧 넘을 수 있을거라 생각한다. 이렇게 말하는 순간에도 순위가 계속 오르고 있어서, 운이 좋으면 2000을 넘을 수 있을지도 모르겠다. 추가 : 아침에 일어나보니 순위가 200등이나 상승했다. ㄷㄷ Prob. A $a..
[BOJ 20188] 등산 마니아 20188번: 등산 마니아 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오 www.acmicpc.net 무난한 트리 DP라고 생각했는데 풀고 나니 DP를 쓰지 않았더라. 나처럼 푼 사람이 거의 없는 듯해서 풀이를 한번 소개해보려 한다. (어쩐지 어렵더라) 더보기 풀이의 전체적인 틀은 트리 dp할 때와 비슷하다. dfs를 돌면서 서브 트리에 대해 문제를 해결한 다음, 이를 합쳐서 전체 트리에 대한 문제를 해결한다. 하지만 이때 서브 트리에서 전해주는 값이 조금 다를 뿐이다. 다음과 같은 상황을 가정해보자. 깊이가 $d$인 노드 $p$를 루트 노드로 하는 서브 트..
Educational Codeforces Round 111 (Div. 2) Dashboard - Educational Codeforces Round 111 (Rated for Div. 2) - Codeforces codeforces.com 2시간 동안 고작 3문제 푼 게 끝인데 지금까지 받아보지 못했던 퍼포를 받았다. 에듀 치고는 어려운 셋이었나 보다. 상승 폭을 보니 맥스 레이팅을 찍을 것 같아서 조금은 기쁘다. 퍼플은 언제쯤 갈 수 있을까... Prob. A $ ans^{2}\geq n $ 인 $ ans $를 구하면 된다. 왠지는 모른다. ㅋㅋ 인터넷 문제로 제출이 1분 정도 늦어져서 슬펐다. Prob. B 처음에는 case work인 줄 알고 a, b의 범위를 나눠서 생각하고 있었다. 하지만 쓸데없는 짓이었고, a가 항상 n번 더해진다는 것을 알면 b의 범위만 고려해주면 ..
21.07.13 요즘 너무 해이해졌다. 갑작스럽게 집에 왔기 때문일까? 성적으로 터진 멘탈은 어느 정도 회복된 것 같지만 여전히 공부는 하지 않고 있다. 평소 같았으면 새로운 알고리즘을 배우느라 정신없었을 텐데, 지금은 재밌는 게임과 웹툰을 찾는 데에 온종일 시간만 허비하고 있다. 당장 NYPC와 정올 2차 준비를 해야 한다는 것을 잘 알고 있지만, 코딩을 안 하다 보니 실력도 떨어지고 그래서 더 안 하게 되는 것 같다. 그래서 지금부터라도 마음 먹고 다시 시작해보려 한다. 솔직히 폰만 보지 않으면 시간은 넘쳐난다. 하루 목표는 다음과 같다. - 브론즈 10문제, 실버 10문제 해결, 골드 5문제, 플레 1문제 해결 21.07.14 수정 : 무리였다;; 5/5/5/1로 정정한다. 21.08.06 추가 : 역시나 이것도 ..
경로 가중치 합 hld 구현 코드 특징 : 맞는지 모름 앳코더에서 Proof by AC 성공 #include using namespace std; #define fastio cin.tie(0)->sync_with_stdio(0) #define X first #define Y second typedef pair pii; const int N=1e5+1; struct Segment { int a[N]; int tree[4*N],lazy[4*N]; void init(int l,int r,int i) { if(l==r) { tree[i]=a[l]; return; } int m=l+r>>1; init(l,m,i