본문 바로가기

전체 글

 (175)
Diamond II 달성 레이지 세그를 배우고 나서 세그 비츠를 잡았고 생각보다 공부가 빨리 끝났다. 사실 시간 복잡도 증명은 느낌만 알고 넘어가긴 했는데, 갓들도 이해를 완벽히 하신 것은 아닌 것 같아서 그냥 넘어가기로 했다. (이러면 경험치 날먹 아닌가?) 2021.06.05 추가 : https://algoshitpo.github.io/2020/03/23/PotentialMethod/ 읽어보자. 그리고 세그 비츠 덕분에 자료구조 경험치가 떡!상해서 solved.ac 시작 이후 처음으로 수학 태그가 경험치 2등의 자리로 내려왔다. 수학은 나의 상징이자 자존심이었는데 자료구조한테 진걸 보자니 조금 속상했다... 조만간 날 잡고 수학 셋을 밀어야겠다.
Segment Tree and Lazy Propagation 드디어 느리게 갱신하는 세그먼트 트리의 구현을 끝냈다. update에서 r을 e로 쓴 오타를 몇 시간동안 찾지 못해 고생했다. 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net #include using namespace std; #define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) typedef long long ll; const int N=1e6+1; struct Segment { ll ..
Class 8 취득 상당히 교육적이고 하드했던 셋이었다. 기존에는 10문제 정도가 풀려 있었고, 약 2주 전부터 class 8을 밀기 위한 공부를 한 것 같다. 전체적으로 문제들의 질이 높아서 전혀 지루하지 않게 풀 수 있었다. 아직 pbs의 이해가 부족하고, hld와 pst의 이론과 구현이 부족하니 이 부분을 보완해서 클래스 8을 끝까지 밀어보자.
Codeforces Round #722 (Div. 2) Dashboard - Codeforces Round #722 (Div. 2) - Codeforces codeforces.com 코포 금단증이 점점 심해지던 차에 내가 선호하는 Div1+Div2 라운드가 나와서 기분 좋게 신청했다. 대회 당시 코 앞에 닥친 수행이 한두 개가 아니었는데, 이번 라운드는 절대 놓치고 싶지 않다는 생각이 들어 수행은 머릿속에서 지워버렸다. 그 여파로 대회가 끝나고 며칠 뒤인 지금 후기를 쓴다. 물론 지금도 밀린 수행이 쌓여있지만 난 모르겠다. 어떻게든 되겠지. Prob. A 최솟값이 몇 개인지 구하는 문제. 오랜만에 하는 대회이다 보니 문제가 잘 안 읽혀서 당황했다. Prob. B 수학 느낌 나는 문제. 정확하지 않은 풀이 몇 개가 생각났는데 솔브 수가 빠르게 늘어나길래 그냥 ..
연속합 최대 Segment Tree 말 그대로 구간에서 최대 연속합을 구해주는 세그먼트 트리이다. 금광 세그로 유명하고, 금광 문제를 풀기 위해 배웠다. 아이디어가 신기함! 진한님의 코드를 적극 참고했습니다. 16993번: 연속합과 쿼리 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j : Ai, Ai+1, ..., Aj에서 가장 큰 연속합을 출력한다. (1 ≤ i ≤ j ≤ N) 수열의 인덱스는 1부터 시작 www.acmicpc.net #include using namespace std; #define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) typedef long long ll; const ll INF=1e18; ..

티스토리툴바