돌이 코딩하는 방

문제 링크 : 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그룹에서도 똑같은 방법으로 답이 될 수 없는 숫자 쌍 들을 고를 수 있다. 이렇게 숫자 쌍으로 묶고 나니까 좌표평면이 생각나게 되었다. 숫자 쌍을 좌표평면 상의 점으로 대입해서 생각하게 되면, 문제를 좀 더 직..

문제 링크 : www.acmicpc.net/problem/13361 문제 풀이 이 문제를 풀기 위해서는 아주 간단하지만 핵심적인 관점 바꾸기를 하나 해야한다. '뒤집어서 생각하기' 우리가 구하고자 하는 것은 가장 긴 세로의 길이의 합이다. 근데 이는 전체에서 가장 짧은 가로 길이의 합을 뺀 것과 같다. 만약 이 문제가 같은 길이로도 이어 붙일 수 있었으면 어땠을까? 굉장히 쉬운 문제가 되었을 것이다. 그냥 모든 판을 길이가 짧은 쪽을 가로로 돌린다. 임의의 정수 집합은 같거나 작아지는 순서대로 배치 할 수 있기 때문에 항상 작은 쪽을 가로로 선택해도 조건에 맞게 해결을 할 수 있게 된다. 하지만 본 문제에서는 같은 길이도 선택을 할 수 가 없다. 이 부분이 핵심이고, 따라서 판들을 같은 길이가 존재하는 ..

문제 링크 : www.acmicpc.net/problem/18251 문제 풀이 이 문제를 보자마자 연관성이 큰 다른문제가 떠오르게 되었다. 문제 링크는 기억이 안나지만 설명을 하자면, 수열이 주어지고 그 수열에서의 부분 최댓값을 구하는 문제이다. 이 문제는 앞에서 부터 계속 더하면서 최댓값을 관리하고 값이 음수가 되었다면 중간에 계속 0으로 초기화 시키는 것을 반복하는 것으로 $O(N)$에 풀 수 있다. 다시 이 문제를 살펴보자. 이 문제와 위에서 설명한 문제의 차이점은 높이가 있다는 것이다. 하지만 전체 노드들의 왼쪽에서 부터 오른쪽으로의 순서는 정해져 있다. 그리고 높이는 lgN이다. 직사각형의 윗변과 아랫변을 정해보자. 이 때 나올 수 있는 경우의 수는 $lg^2N$개이다. 그 두 변 사이에 있는 ..

Codeforces 코드포스는 한 동안 쉬었다. 솔직히 내 실력이 만약 떨어졌다면 가장 큰 원인은 꾸준히 코드포스를 하지 않았기 때문이라고 할 수 있다. 하지만, 코드포스에 시간이 안 맞는 것도 컷다. 할일도 꽤나 많았고, 시간대가 애매했다. 최근에는 너무 코포를 안했다고 느껴서 레이티드 버츄얼을 돌리고 있다. 그래도 아직 무난하게 오렌지 실력은 나오고 있다. BOJ & Solved.ac 약 40문제 정도를 풀었다. 많지는 않은 수치이지만 꽤나 어려운 문제들을 위주로 풀었다. 특히 한 동안은 solved.ac의 class 9 에센셜 문제들을 위주로 풀었다. class 9 에센셜 24문제중 15 문제를 풀었다. 경험치는 많이 안오른 것처럼 보이지만 사실 제작한 문제와 세그트리 등의 많은 문제등의 경험치가 ..

문제 링크 : www.acmicpc.net/problem/14898문제 태그 더보기 persistent segment tree문제 풀이꽤나 오래 고민했지만, 풀이가 감이 안잡혔다. 그래서 힌트를 받았고 [1,i] 구간이라는 힌트를 얻게 되었다. 모든 [1,i]구간에 대해서 서로 다른 수의 개수를 가지고 있는 것은 어렵지 않게 해낼 수 있다. 하지만 우리가 필요한 것은 [i,j] 구간에 대한 서로 다른 수의 개수다. 여기서 한가지 아이디어를 생각해냈다. [1,i] 구간에서 각 수별로 가장 오른쪽에 있는 수들만 가지고 있는 것이다. 즉, [1,i] 구간에서 가장 오른쪽에 있는 1, 가장 오른쪽에 있는 2, ... 들을 가지고 있는 것이다. 이렇게 되면 쿼리로 [a,b] 에 대한 질문이 들어오면, [1,b] ..

내 인생 처음이자 마지막 KOI 본선... 준비를 좀 덜 했다고 하더라도, 실력이 좀 줄었다고 하더라도 안할 수는 없었다. 나름 역대 koi 2차 문제들을 3개 빼고 다 풀기도 하는 등, 열심히 준비를 했다. 긴장되는 마음가짐을 최대한 억누르려고 했고, 나에게 크게 중요한 대회는 아니라는 마인드 컨트롤을 하였다. 사전 준비 대회는 1시 30분에 시작이었고, 1시부터 준비할 수 있는 시간을 가졌다. 그런데 키보드가 너무 불편했다. 내 노트북 키보드가 굉장히 특이한 형태인데, 그 키보드에 익숙해져버려서, 다른 키보드에 손이 잘 안익게 되었다. 앞으로는 항상 키보드를 들고 다닐까 생각을 하고 있다. 아무튼 스페이스바가 아예 안되는 컴퓨터가 있어 옆 컴퓨터에서 시험을 보게 되었다. 연습 문제는 예선 2교시 1번..

이번에 소개할 내용은 Persistent Segment Tree이다. Segment Tree 의 한 종류로 굉장히 특별한 부분을 맡고 있다. Persistent Segment Tree의 사용 이 문제를 보자. www.acmicpc.net/problem/16978 물론 오프라인이기 때문에 쓸 수 있는 테크닉으로 풀 수도 있지만, 이 문제가 주어진 쿼리를 순서대로 대답해야하는 온라인 문제라고 생각을 해보자. 일단은 세그먼트 트리를 사용할 것이다. 그런데 우리는 임의의 k에 대해서 k번째 쿼리까지만 의해서만 바뀐 그 시점의 세그먼트 트리를 알고 싶다. 가장 직관적인 방법은 모든 k에 대한 세그트리의 상황을 저장해 놓는 것이다. 하지만 O(QN)의 시간과 공간 복잡도가 필요할 것이고, 당연히 Q와 N은 1000..

문제 링크 : www.acmicpc.net/problem/10806 문제 풀이 step 1 그래프에서 가장 먼저 생각했던 것은 사이클의 관찰이었다. 사이클에서는 어떠한 간선을 한 개 끊어도 임의의 정점에서 다른 정점으로 이동할 수 있다. 또한, 사이클 내의 한 정점이 간선 하나를 끊어도 다른 정점 a에 갈 수 있다면, 사이클 내의 임의의 정점은 간선 하나를 끊어도 정점 a에 갈 수 있다. 이 관찰을 하니까 connecting supertrees라는 문제가 생각났고, 사이클을 하나의 정점으로 치환해야겠다는 생각이 들었다. 처음 주어진 그래프에서 사이클을 계속해서 정점으로 치환하면 트리가 된다. 그 트리에서 최소환의 간선을 추가해서 사이클을 정점으로 바꾸는 연산을 계속 할 때 결국 한 개의 정점만을 남겨야 ..

문제 링크 :www.acmicpc.net/problem/8217 문제 태크 더보기 PBS, Segment Tree 문제 풀이 이 문제에 사용되어질 알고리즘을 어느정도 스포를 당하고 시작했다. 하지만 내가 딱 1번밖에 짜보지 못했던 알고리즘이고, 문제가 꽤나 웰노운이라고 들어서, 풀이의 나머지 부분을 완성하려고 하였다. pbs를 통해서 분리 횟수가 logQ이고 한 번 분리할 때마다 판별을 N개 해야하기 때문에 벌써 $O(NlgQ)$라는 시간복잡도가 형성되었다. 그래서 나의 1차 목표는 1개의 국가에 대해서 특정한 시점에 대해서 O(1) 만에 그 시점에 정해진 운석량을 모았는지 판별하는 것이다. 혹은 log의 시간복잡도에 해야할 것이다. 하지만 구간 쿼리가 주어지기 때문에 너무 Segment Tree를 쓰고..