구사과

https://docs.google.com/spreadsheets/d/1-kY6uiLOo1AKSBCSjbpGRBZbIldO_3dg6oTRKIJzT-g/edit#gid=0주요 OI 문제들을 연도별로 정리해서, Google Docs 문서로 정리해 보았다. 저렇게 표까지 만든 건 IOI 2017 멘토 / 합숙 교육에서 사용하기 위함이었고, 추후 교육에서도 사용될 수 있을 것 같다. 이 표가 가장 유용할 만한 타겟은 IOI를 국가 대표 레벨에서 대비하는 학생들이라고 생각한다. 하지만, ICPC 세계 대회 등 굳이 정보올림피아드를 준비하지 않는 입장에서도 충분히 풀어볼만한 문제들이라고 생각한다. 나의 경우만 해도 여전히 저러한 문제들을 ICPC 문제들보다 우선해서 공부하고 있다.공부에 유용한 자료가 되길 바란다...

1. 평균값 수열수열의 초항 S1을 결정했다 하면, S2 ... SN까지 모든 숫자들이 도미노처럼 결정된다. S_{i+1} = 2 * m_i - S_i 이기 때문이다. 고로, S1을 결정하면 모든 수열의 원소를 알 수 있고, 이들이 단조 증가 하는지만 체크해 주면 된다. 모든 S1을 다 해 볼 수 없으니, 대신 S1 = x라고 두고 부등식을 계속 쓰는 식으로 x가 답이 될 필요 충분 조건을 찾아보자. 이렇게 했을 때, 수열은 {x, 2m1 - x, 2m2 - 2m1 + x, 2m3 - 2m2 + 2m1 - x ... } 과 같은 형태로 구해진다. 단조 증가한다는 것은 인접한 항들이 모두

1. Vouchers각각의 상자에 voucher의 번호를 적어놓은 후, 모든 배수를 순회하는 단순한 접근법으로 접근한다면, 쿼리당 O(n)의 시간이 걸리고 시간 초과가 날 것이다. 하지만, 에라토스테네스의 체만 생각해 봐도 줄일 여지가 충분하다. 모든 배수들을 열거하는 데 드는 시간은 O(n)이 아니라 O(n / a_i) 이기 때문이다. 고로 쿼리로 주어지는 모든 숫자가 다르기만 해도 O(nlgn) 시간 복잡도를 보장할 수 있다. O(n/1 + n/2 + n/3 + ... + n/n) = O(nlgn)이기 때문이다.쿼리로 같은 숫자가 여럿 들어온다 하더라도 문제가 크게 달라지지 않는다. X번 쿼리로 가져간 최대 번호의 상자가 last_X번이라면, 다음 번에 볼 때 X ~ last_X 번의 상자들은 볼 필..

1. Mountain RoadA 타입 차와 B 타입 차를 분리시키고 생각해 보자. 각각의 그룹에서 먼저 도착한 순서대로 차들을 처리해야 하니, A 차가 현재 몇 대 까지 / B 차가 현재 몇 대 까지 처리되었는지 정도의 상태로 DP를 돌려보자.A와 B가 항상 교차해서 나온다면 단순히 끝나는 시간만을 고려해주면 되겠지만, 실제로 A 차가 연속하거나 B 차가 연속할 경우에는 일련의 추가적인 규칙들이 있다. 고로, 현재의 DP 상태에서 연속한 A 차를 추가하거나, 연속한 B 차를 추가해서 새로운 DP 상태의 시간을 계산해야 한다. 또한, 마지막에 A를 썼는데 거기에 연속한 A 차들을 추가하면 계산이 꼬이니, 현재의 DP 상태는 단순히 차를 몇 대 쓴 것만이 아니라, 마지막에 무슨 차를 썼는지 역시 저장해야 한..

1. 텔레점프아이디어의 큰 틀은 생각보다 간단하다. 다만 이를 실제로 완성하는 건 꽤 까다로운 문제이다. * 먼저 처음에 A 에지 하나와 B 에지 모두를 소모해서, 앞 부분의 점을 다 연결 시켜준다. 1 - 2 / 1 - 3 / 2 - 4 / 3 - 5 ... * 이제 A 에지와 C 에지만이 남았다. B 에지로 만든 path의 두 끝 점 중 하나는 버리고 (즉 시작점으로 하고), 나머지 하나를 이어나갈 것인데, P / P + 3 / P + 6 ... 이런 식으로 이으면 중간에 공백이 생기니, A 에지를 하나 사용해서 P + 1 - P + 2를 이어주고, P + 1 / P + 4 ... 혹은 P + 2 / P + 5 ... 를 계속 이어준다. C 에지를 전부 소모할 때까지 이를 계속한다. * 남은 에지들은..

1. ČVENK점 (x, y)가 빈 공간이기 위해서는 x & y = 0이 성립해야 한다. 이 점에서는 항상 (0, 0)으로 가는 경로가 존재하는데, 다음과 같은 방법으로 이를 찾을 수 있다. * x == 0 || y == 0일 경우에는 자명하게 경로를 찾을 수 있다. * x와 y가 모두 0이 아니라고 가정하자. lowest significant bit (LSB) 가 작은 쪽을 찾자. 여기서는 일반성을 잃지 않고 x라고 한다. 그렇다면, (x - LSB(x), y) - (x, y) 를 잇는 경로는 비어 있다. (x - LSB(x), y) 에서 재귀적으로 계속 경로를 찾아나간다.이 경로는 항상 존재하며 유일하다. 이는 빈 공간들이 트리를 이룬다는 증명이 되기도 한다. (사실 그건 사진을 보면 쉽게 눈치챌 수..

1. 숫자카드간단한 동적 계획법이다. 문자열을 길이 1 / 길이 2의 문자열로 분해하는 경우의 수를 세는 것인데, dp[i] = 앞 i자리 문자를 모두 분해하는 경우의 수라고 하면, dp[i-1]과 dp[i-2]에 대한 점화식이 나오고, 이를 통해 해결할 수 있다. 2. 놀이공원배열을 통해서 각 1분 단위의 시간에 휴식이 가능한지를 관리한다. 놀이기구 하나에 대해서, (시작 시간 - 10분) ~ (종료 시간 + 10분) 동안은 휴식이 불가능하다. 고로 각 놀이기구 마다 이 구간에 체크해 두면, 해당 단위 시간에 휴식이 가능한 지 알 수 있다. 이 정보를 안다면, 이 정보를 안다면, 가장 긴 휴식 가능 구간을 구하는 문제는, 0과 1로 이루어진 배열에서, 가장 긴 0으로 이루어진 연속 구간을 구하는 문제가..

1. 워크스테이션 배정그리디 알고리즘으로 해결할 수 있다. 모든 배정을 시작점 순으로 정렬하자. i번 배정을 할 때, 만약에 이미 끝난 다른 배정 중, 끝난 시간과 현재 시간과의 M 이하인 것이 있다면 그 배정과 같은 워크스테이션을 쓴다고 생각하자. 만약에 그러한 배정이 여럿 있다면 차이를 최대화 하는 것이 이득이다. (차이를 괜히 작게 줘 봤자 시작점이 큰 다른 배정에게 도움이 안 되니까) 이러한 그리디 알고리즘을 priority queue 등으로 구현하면 O(nlgn)에 문제를 해결할 수 있다. 2. Identifying Map Tiles주어진 문자열을 비트마스크로 읽어서 출력하면 되는 단순 구현 문제이다. (사실 1번 2번은 일단 placeholder로 넣은 거였습니다. 즉 나중에 다른 문제로 고칠..

1. Kralj원형 구조에서 푸는 문제들은 그대로 풀면 짜증나거나 어려운 경우들이 많기 때문에 선형 구조로 환원시키는 것이 중요하다. 이 문제에서도 그러한 것이 가능하다. 어떠한 자리 i에 대해서, 어떤 몬스터들은 그 자리에 앉기 위해 달려들 것이고, 어떤 몬스터들은 그 자리에 실제로 앉을 것이다. flux(i) = (i번째 자리에 앉으려고 온 몬스터의 수) - 1이라고 하자. 1은 그 자리에 실제로 앉아서 싸우는 몬스터를 뜻한다. flux(i)의 부분합을 한번 그래프로 그려보자. 0점에서 올라갔다 내려갔다 했다가 다시 0점으로 오게 될 것이다. 이 중 최소를 찍는 위치가 있는데, 여기를 중심으로 왼쪽과 오른쪽 구간을 바꿔보자 (cyclic shift). 그렇다면, 이 그래프는 0점에서 올라가다가 내려가..

1. 점 고르기모든 n^2개의 점을 잡아서, 두 점을 최대 / 최소로 하는 직사각형이 존재할 수 있는지를 판별하면 간단하게 풀 수 있다. 이 존재성은 단순한 O(1) 식으로 판단할 수 있어서, 시간 복잡도는 n^2이다. 난 n^2lgn에 풀었는데 내 풀이는 부끄러우니 설명을 생략한다... 2. Number SetsP 이상의 모든 prime factor를 열거해야 할 것 같지만, 실제로 필요한 건 P 이상 1000000 이하의 prime factor 뿐이다. 1000001 이상의 prime factor는 중요하지 않은 게, B - A