돌이 코딩하는 방

문제 링크 : https://www.acmicpc.net/problem/25351 문제 풀이 part 1 이후로 f(p)는 구간 p에 대한 중간 원소 인덱스 합을 의미한다. 또한 (a,b) 는 닫힌 구간 [a,b] 를 의미한다. 선공과 후공이 고를 수 에 대해서 생각해보자. T번째 판은 [a,b] 에서 진행된다. 두 개의 구간 p와 q에 대해서 p가 q에 속한다면 f(p)

문제 링크 : https://www.acmicpc.net/problem/10350 문제 풀이 맨처음에 문제를 딱 보고서 떠오른 생각은 가장 작은 값에서 "행동" 을 실행하는 것을 반복하면 될 것이라고 생각했다. exchange argument에 의해서 가장 작은 값의 위치에서 실행하는 것이 더 손해를 볼 일은 없다고 생각했다. 그래서 좀 더 고민을 해보다가 다른 생각이 떠오르지 않아 구현을 시작했고, 결과는 pq에 담으니 mle가 뜨게 되었다. 이를 보고서 절댓값의 감소량을 추적해보니 얼마 되지 않는다는 것을 알 수 있었다. 따라서 답은 굉장히 크다는 것을 알 수 있었고, 어떻게 해도 직접 "행동"을 한 번씩 해가면서 변화를 보는 것은 답이 될 수 없겠다고 판단하였다. 이 상황에서 내가 나아갈 수 있는 ..

요즘 codeforces 에서 문제를 푸느라고 한동안 블로그 글을 쓰지 않았다... 다시 백준에서 문제를 조금 풀게 된 만큼 한 번씩 글을 써야겠다. 문제 링크 : https://www.acmicpc.net/problem/9208 문제 풀이 (의식의 흐름) ※ 제 풀이는 intended solution에서 좀 벗어난 풀이입니다. 관련 개념 및 의도 된 풀이를 보고 싶으시면 https://qwerasdfzxcl.tistory.com/11 를 참고해주세요. 문제의 첫 방향성을 잡는 것이 힘들었다. 관찰의 실마리도 별로 보이지 않았으며, 무엇을 사용해야겠다는 감도 잡히지 않았다. 그렇기 때문에 일단 문제를 직선에서 풀기로 생각하였다. 원형 문제는 보통 길이를 두 배로 하여 직선으로 바꿀 수 있기 때문에, 그리..

나는 검수자로서, 대회 주최자로서 언젠가는 boj 22847 - 루미너스와 모험 중 마주친 퍼즐게임을 풀겠다는 의지를 잡고 있었다. 하지만, 엄두는 나지 않았다. 그와중에 주위에서 몇몇 분들이 풀겠다는 의지를 비쳤고, 그에 힘입어 나도 도전을 하였다. 이 글을 루미너스의 공식 풀이를 본 분들에게 바칩니다... 공식 풀이에서 사용된 용어와 파트를 가지고 설명합니다. 수도 없는 시간의 고민 끝에 나온 공식 풀이지만, 이를 구현하는 것은 너무나도 힘들 것 같았다. 특히 c 구역에 경우에 따라서 나누는 부분 앞에서 나는 구현할 의지를 잃었고, 그 경우를 하나로 통합하는 방법을 고민했다. 결론을 말하자면 C 구역에 D가 있는 모든 경우를 굉장히 비슷한 두 경우로 나누는 것에 성공했다. 이제부터 이에 대해 설명하려..

문제 링크 : https://www.acmicpc.net/problem/18721 문제 태그 더보기 세그먼트 트리 문제 풀이 와... 미친 아이디어 문제이다. 솔직히 자력으로는 정말 풀기 힘든 문제라고 생각한다. 어쩌면 수올러들이 생각할 확률이 더 높을 수 있다. 그런 느낌의 풀이이다. 왠만하면 오래 고민해보고 이 글을 읽는 것을 추천드리며, 이 글을 읽을 때도 풀이의 일부씩만 보고 다음 직접 풀이를 완성하면 훨씬 좋을 것 같다. 처음에 1주일동안 생각했다가 도저히 떠오르지 않아서 풀이의 첫줄을 보았다. "한 호를 잡아 정답이 되는 세트의 가장 작은 호라고 생각해보자" 이 문장에 대해서 곰곰히 생각해 보니까 풀이가 서서히 확장되기 시작했다. 이 글과 같이 분석을 해보면 지정한 호와 다른 호들의 관계를 분..

문제 링크 : www.acmicpc.net/problem/12876 문제 태그 더보기 Offline dynamic Connectivity , Lichao Tree 문제 풀이 보통 반평면 땅따먹기 1은 풀고 올 것이니 이에 대한 풀이는 알고 있다고 가정하려고 한다. 반평면 땅따먹기 1은 그냥 일반적인 cht optimization이 아니라 직선의 기울기의 단조성이 없기 때문에 lichao tree를 써야하는 문제였다. 반평면 땅따먹기 2에서는 이제 선분이 중간에 없어진다. 선분에 life가 존재하게 되었다 이러한 문제는 offline dynamic connectivity로 풀 수 있다. lichao tree에서 선분이 추가될 때, 노드를 내려가면서 여러개의 노드를 업데이트 하게 된다. 그 과정에서 노드의 ..

문제 링크 : www.acmicpc.net/problem/20060 문제 여담 : 3년전에 뉴비 시절때 보자마자 무서워서 도망갔다. 쉬운 문제라는데 이런 함수 구현 형태를 접해본적도 없고, 너무 어렵게 느껴졌다. 슬펐었다. 문제 풀이 제일 먼저 생각할 수 있는 것은 첫 글자를 빠르게 찾아야 한다는 것이다. 총 글자의 수는 4가지 이기 때문에 AB,AX를 묶어서 2번 탐색하는 것으로 첫번째 글자를 찾을 수 있다. 일반성을 잃지 않고 A였다고 하자. 이제 우리는 N번의 탐색을 통해 N-1개의 글자를 찾아야 하며, 한번 탐색때 부를 수 있는 단어의 길이는 4N이다. 길이와 횟수가 비슷하기 때문에 1번에 1개의 글자를 알아내는 것을 목표로 해야 한다. 한번의 질문의 대한 답으로 B,X,Y 중 다음글자가 무엇인지..

문제 링크 : www.acmicpc.net/problem/11738 문제 설명 다각형이 삼각분할 되어있다. 모든 선분의 길이는 1이다. 쿼리로 두 점이 주어졌을 때 두 점 사이의 거리를 출력하는 문제이다. 문제 태그 더보기 bfs, dnc, offline query, 재귀 문제 풀이 이 문제를 보면 가장 먼저 $O(NM)$ 의 풀이를 생각할 수 있다. 본인은 n개의 점에서 모두 다익스트라를 돌려서 $O(NMlgN)$의 풀이를 생각했지만 모든 선분의 가중치가 1이기 때문에 모든 점을 시작점으로 해서 각각 bfs를 하는 것으로 $O(NM)$의 풀이가 나오게 된다. 하지만 문제에서 요구하는 시간 복잡도는 제곱 미만이다. 따라서 이 문제의 특성을 관찰해야 한다. 이 문제의 가장 큰 특성은 일반적인 그래프가 아닌..

문제 링크 : www.acmicpc.net/problem/3408 문제 힌트 1. 모든 부분 배열에 대해서 non-boring 한지 확인할 수 있을까? 2. 모든 non-boring 한 배열에는 unique한 원소가 존재한다. 더보기 3. unique 한 원소를 포함한 모든 부분 배열은 non-boring 하다. 4. 순서를 잘 바꿈으로써 시간 복잡도를 만족시킬 수 있다. 문제 풀이 -스포 주의- 더보기 우리의 목표는 모든 부분 배열에 대해서 그 부분 배열이 non-boring 한지를 알아내는 것이다. 이에 앞서 우리는 모든 원소에 대해서 그 원소와 같은 값을 가지는 바로 왼쪽 원소와 오른쪽 원소의 위치를 모든 원소에 대해서 저장하고 있을 것이다. 첫번째로 구간을 배열 전체로 설정하자. 이 배열이 non..

문제 링크 : www.acmicpc.net/problem/14636 문제 풀이 호드를 위한 돈. 이 문제를 처음보면 꽤나 직관적이라는 것을 알 수 있다. A그룹에서 숫자 쌍 하나, B그룹에서 숫자 쌍 하나를 꺼내 수 차이의 곱을 최대화 시키는 것이다. 여기서 가장 쉽게 생각할 수 있는 것은 A그룹에서는 숫자쌍이 작을 수록 이득이라는 것과 B그룹에서는 숫자쌍이 클수록 이득이라는 것. 즉 A그룹에 (1,3),(2,5)가 있으면 (1,3)이 상위호환이기 때문에 (2,5)는 절때 답을 만들 수 없으며, B그룹에서도 똑같은 방법으로 답이 될 수 없는 숫자 쌍 들을 고를 수 있다. 이렇게 숫자 쌍으로 묶고 나니까 좌표평면이 생각나게 되었다. 숫자 쌍을 좌표평면 상의 점으로 대입해서 생각하게 되면, 문제를 좀 더 직..