본문 바로가기

전체 글

 (175)
비서 문제 코드 #include using namespace std; int n,x,cnt; vector chk; vector v; void bt(int i) { if(i>n){ int mx=0; for(int i=1;i
Li Chao Tree 리차오 트리 특: CHT를 사용할 때 필요한 기울기의 단조성이 없어도 된다. 트리 안에 식(흔히 일차함수)을 넣는 것과 점 최소/최대 쿼리를 O(logN)에 해주는 자료구조. 외우기 쉽고 범용성도 좋아 유용할 것 같다는 생각이 든다. CHT로 풀리는 문제는 시간이 빡빡하지 않은 이상 리차오 트리로도 풀린다. 12795번: 반평면 땅따먹기 첫 줄에는 게임을 진행한 정보의 개수 Q(1 ≤ Q ≤ 200,000)이 주어지며, 이어서 Q 줄에 걸쳐 각 정보가 주어진다. 각 줄의 첫 번째 숫자가 1일 경우 이어서 2개의 정수 a, b(|a| ≤ 1,000,000, |b| ≤ 1,000,000, www.acmicpc.net #include using namespace std; #define fastio ios::s..
2021 KOI 1차 가채점 결과 상위 3.481%(26등)로 은상을 받았다. 예상했던 것보다 높은 등수여서 놀랐고, 본선에서 더욱 잘하고 싶다는 욕심이 생겼다. 수상 여부와 상관없이 이번 KOI 예선을 치른 모든 분에게 수고했다는 말씀을 드리고 싶고, 본인이 원하는 성적이 나오지 않았더라도 실망하지 않고 더욱 성장하는 계기가 되었으면 좋겠습니다.
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 - 피자굽기 오븐의 모양을..

티스토리툴바