본문 바로가기

전체 글

 (162)
KOI 2021 1차 후기 KOI 1차 예선이 끝났다. 예상 점수는 421(수정: 406.8)점으로 만족스럽지는 않지만 그래도 받을 만큼 받은 것 같다. 사실 KOI 1차 대비 셋이 2개가 더 있었는데, 시간 관계상 올리지 않는 것으로 혼자 합의 봤다. 1교시 문제가 20개나 있어서 상당히 놀랐지만, 앞쪽의 문제들이 쉬워서 시간이 부족하지는 않았다. 스토리가 있는 문제들만 언급하겠다. 10. 중심 노드 찾기 : n*(n-1)/2 로 찍고 검토하지 않아 틀렸다. 그런데 지금 생각해봐도 n-1이 어떻게 가능한지 모르겠다. 조금 생각해보면 쿼리 한 번마다 후보 노드 하나를 제거할 수 있다. 12. 사각형 세기 : 이걸 틀려놨다. 24가 너무 적은 것 같은 느낌은 들었지만 눈을 씻고 봐도 더는 안 보였다... 대회 끝나고 보니 큰 다이아..
2021 KOI 대비 DAY-2 최근에 정말 파도처럼 밀려오는 수행평가 덕분에 정신없이 살고 있다. 그와중에도 축구와 PS를 꾸준히 하고 있기는 하지만... 뭐 그렇다. KOI가 이틀 남은 시점에서 대비가 전혀 안되었다는 것을 느끼고 있지만 다른 일정들을 포기할 수가 없어서 KOI가 뒷전으로 밀리고 있다.. 이번 셋은 한참 전에 풀었지만 블로그 작성을 계속 미루다가 KOI가 끝난 뒤에 올리기는 조금 그렇다고 생각해서 급하게 풀이?를 작성하려고 한다. A - 방 배정하기 O(N^3) 브루트포스로 해결 가능하지만, O(N) DP가 먼저 보였다. B - 자리 배정 뇌절 달팽이 구현. 대충 야매로 풀었다. C - 토마토 단순 BFS. 풀이는 알지만 구현하고 싶지 않다. 개인적인 의견이지만 골드 가도 될 것 같다. D - 피자굽기 오븐의 모양을..
2021 KOI 대비 DAY-1 오랜만에 글을 쓴다. 지난 일주일 동안 열심히 노느라 PS에도, 블로그에도 조금 소홀했다. 저녁시간에 축구 또는 농구를 하고 조기 입실을 한 다음, 라면과 컵밥을 먹고 게임을 하다가 11시 조금 넘어서 올라오는 웹툰을 보면서 잠드는 행복한 일상의 반복이었다. 물론 PS를 완전 놓지는 않았다! 레이지 세그 구현체를 만들려고 보니 전부 탑다운 세그 트리를 이용하길래 탑다운 세그 트리 구현체를 먼저 만들려고 시도했지만, 마음에 드는 구현체를 만들기가 쉽지 않아 포기했을 뿐이다. (struct에 나름 최적화가 되어있으면서도 직관적으로 이해 가능한 그런 구현체가 있다면 공유 부탁드립니다 ㅠ) 정신을 차리고 보니 KOI 예선이 2주 앞으로 다가와서 정말 대비를 해야겠다고 생각하던 차에, 북곽 선생님들께서 졸업하신 ..
알고리즘 공부 계획 지난 금요일에 시험이 끝났고, 이번 주말 동안엔 잠깐 쉬는 겸 해서 다이아(정수론+그리디)를 파밍했다. '수(Hard)' 이 녀석을 풀고 싶었지만 도저히 생각이 안 나서 다음에 다시 생각해보기로 했다. 이제 학교를 들어가면 수행 몇 개가 준비되어 있지만, 가볍게 무시해주고 전부터 공부하고 싶었던 알고리즘들을 배워볼 예정이다. 먼저 수개월을 미루고 있는 레이지 프로퍼게이션 구현을 끝내고, 개념 상으로만 알고 있던 MST, PST, HLD 구현을 해볼 것이다. 이러고 시간이 남는다면 최근에 컵이가 세그트리 비츠를 배운 것으로 추정되기 때문에, 관련 강의를 들어보고 싶다. 이쯤에서 상기시키는 올해 목표 : 정올 본선 은상 실패 / NYPC 본선 진출 실패 / 코드포스 퍼플 성공 /// ㅂㅅ...
Bottom-Up Segment Tree 2042번: 구간 합 구하기 첫째 줄에 수의 개수 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; struct Segment { vector tree; int n; Segment(int n) : tree(2*n), n(n) {} ll f(ll a,ll b) { return a+b; } void ini..

티스토리툴바