본문 바로가기

전체 글

 (35)
IOI 2013 Game 풀이 (정해와 다른 풀이) 문제내용 : https://www.acmicpc.net/problem/23839 이 문제의 80점짜리 서브태스크까지는 전형적인 2D SegmentTree를 이용하여 풀이할 수 있다. 딱히 소개할 가치가 있지도 않고 쉽게 알아볼 수 있으므로 그 내용은 생략한다. 하지만 100점은 받지 못하는데, 메모리 초과가 나기 때문이다. 정해는 먼가 독특한 테크닉을 사용하여 메모리를 줄이는 것 같은데, 원래 (왼쪽 자식노드,오른쪽 자식노드,값)에 각각 4바이트, 4바이트, 8바이트를 사용하여 한 노드에 16바이트의 메모리가 사용되는데 이것을 12바이트로 줄여서 문제를 풀 수 있는 풀이가 있어서 소개하려고 한다. 그 방법은 매우 간단하다. 다이나믹 세그먼트트리에서 노드가 생성되는 방식을 생각해보자. 어떤 노드가 생성되고..
2021 한국정보올림피아드(KOI) 1차대회 후기 입실이 12시 반까지인줄 알고 12시에 급하게 일어났는데 입실하려고보니 1시 20분까지였다... 그래서 좀 붕뜨고 시작했다. 그러고 뭐 늘 그래왔듯 신분증 확인하고 시험 시작하고 하는 지루한 시간을 버티고 1교시를 시작했다. 11번까진 그냥 쉬웠다. 12번은 잘 세면 된다. 난 덜 세서 틀렸다. 13,14는 쉽다. 15는 케이스를 잘 생각해주면 된다. 16번은 불가능한 점들을 다 걸러주면 된다. 17은 그냥 감각으로 해도 보통 최소인 19번이 가능하고 아니면 슬로프 dp를 손으로 하자. 18은 스프라그 그런디 정리를 이용해 그런디 수를 손으로 구해서 풀자 19는 트리에서 잘 생각해주면 된다. 음수를 뚫고 갈만한지를 보자. 20은 앞에서부터 잘 맞춰주면 된다. 그러고 이제 2교시를 했다. 1번은 그냥 굉장..
2021 국가대표 멘토링 교육 일지 12766. 지사 배정 사실 문제 이해하기가 굉장히 힘들었는데, 해석해보니 일단 지사들을 s개의 그룹으로 묶은 다음에 그룹 내의 각 지사 쌍들끼리 지사1->본부->지사2 하는 경로를 타게 할 때 그 경로 길이의 합을 최소화하는 문제였다. 일단 당연히 (지사->본부+본부->지사 거리)(이후 X라 통칭)를 구해서 저장해둬야 한다. 다익스트라로 쉽게 구현할 수 있다. 그룹 내에서 이 값들의 합에 그룹 내의 지사 수-1을 곱한 것이 그룹 내에서의 총 이동거리가 된다. 이러면 X가 작은 애들일수록 그룹 내의 지사 수가 적은 그룹에 들어가는 것이 이득이다. 그렇다면 각 그룹 내의 지사 수가 정해져있다 할 때 최적전략은 지사 수가 적은 쪽부터 X가 적은 것을 넣는 것이다. 이렇게 되면 관찰할 수 있는 특징이 각 그룹..
2021 국가대표 멘토링 교육 - 2주차 이번 주차부터는 각자 멘토가 배정되어서 문제를 각자 받았다. 나는 4문제를 받았고, 4문제를 모두 풀었다. 사실 그리고 추가문제도 받았는데, 하나도 풀지 못하고 이월되었다. 1. 사수아탕 굉장히 유명한 문제이지만, 여태까지 풀지 못한 문제이다. 기본적인 관찰으로 0을 기준으로 점점 길게 와리가리하는 것이 최적이라는 것을 알 수 있다. 그러면 구간 dp를 해보고 싶은데, dp식을 세우기가 힘들다. 이때 핵심적인 아이디어는 먹는 사탕 개수를 고정하고 문제를 푸는 것이다. 이제 구간의 크기가 k일 때 방문 순서대로 방문 시간을 t1,t2,..tk라 했을 때, 만약 먹는 사탕 개수를 x개로 고정했다고 했을 때 t1+...+tk+(x-k)*tk의 최솟값을 관리하면 k=x일 때는 m*x에서 이 값을 빼주면 답을 구..
2021 국가대표 멘토링 교육 - 1주차 JOISC Day1에서 미친 난이도의 셋에 거하게 맞고 똑-떨당한 뒤 국대교육을 받게 되었다. 많이 안타까웠고 멘탈도 많이 나갔지만 뭐 어쩔 수가 없다;; 1주차 셋은 백준 네 문제 앳코더 한 문제로 다섯 문제를 받았다. 그 중에 한 문제밖에 못 풀었다;; 나 뭐지 1. Trous de Loup 이분탐색을 하고 싶게 생겼으니 이분탐색을 한다. 어떤 고정된 구간을 본다면 그 내부에서 길이가 d이고 합이 최대인 구간을 뽑아내는 것이 이득이다. 이때 앞쪽 구간부터 본다고 하면 덱으로 문제를 최적화할 수 있다. (현재 구간 내에서 가장 합이 최대인 구간을 앞에 두고 자신 뒤에 있는 구간들 중에서는 자기보다 합이 큰 애가 없는 구간들을 인덱스가 단조증가하게 배치하면 된다.) 그럼 결정문제가 O(N)에 풀리고 문제..
BOJ 10089 profit www.acmicpc.net/problem/10089 10089번: Profit Olympiland에는 1부터 N까지의 번호가 붙은 N개의 마을이 있습니다. 그들 중 일부는 서로 직접 연결되어있고, 전체 도로망은 한 도시에서 다른 도시로 가는 경로가 유일하도록 짜여져 있습니다. 거 www.acmicpc.net 문제 내용을 간단하게 요약하면 트리가 있고 우리는 그 위에 하나의 경로를 잡을 것이다. 그런데 트리에는 M개의 경로가 있는데, 각각의 경로를 포함하게 되면 그 경로에 해당하는 주어진 수익을 얻을 수 있다. 이때 얻는 수익을 최대화하면 된다. 정한 경로의 양끝점을 p1,p2라고 하자. p1에서 p2로 이어지는 경로가 어떤 경로를 포함하려면, p1이 그 경로의 한쪽 끝점에서 만들어지는 서브트리에 포함되..
IOI 2012 tournament 이번 선발고사에서 공동 4등...을 해버리며 슈뢰딩거의 국대가 되어버렸다. 국대가 5명일 수는 없으니 이제 또다른 방법으로 국가대표를 선별해야할텐데, 그래서 PS에 인생을 올인 박는 것이 별로 나쁘지 않은 선택이 되는 상황이 되었다. 그리고 학교에 오니 재밌는 할거리가 PS하기밖에 없어서 당분간 PS에 집중하려고 한다. 그래서 일단 집고 풀어본 문제가 IOI 2012 tournament이다. 문제의 내용은 oj.uz/problem/view/IOI12_tournament를 참고하자. 여기서 첫번째로 해야 될 관찰은 마지막 기사의 위치에 따라 [Si,Ei]가 뜻하는 바가 막 변할 것 같지만 그렇지 않다는 것이다. '이긴 기사'가 '패배한 기사'들까지 모두를 대표하고 있다고 생각하자. 이렇게 생각하면 [Si,..
우체국 4 풀이 www.acmicpc.net/problem/18445 18445번: 우체국 4 원형으로 큰 길(순환로)이 뻗어 있고, 길 옆으로 V개의 마을이 자리잡고 있다. 큰 길의 둘레 길이는 정수 L이다. 이 문제에서 큰 길은 0 이상 L-1 이하의 정수가 늘어져 있는 원이고, 각 마을의 위치 www.acmicpc.net 우체국 3의 풀이는 안다는 가정 하에 설명한다. 우체국 3의 풀이는 원형구간에 대한 풀이를 각 점을 시작으로 한 선형구간에 대해 문제를 푸는 것을 N번 반복하여 문제를 풀어낸다. 이렇게 하여 시간복잡도는 O(N^2KlogN)이다. 하지만 굳이 N개를 다 잘라보는 것은 뭔가 손해같다. 특히 K가 클 때 시간이 오래 걸리는데 이때는 분할되는 갯수가 많아서 optimal한 시작점이 최소 K개나 존재한다..

티스토리툴바