구사과

1. 회색 영역해당 데이터가 어떤 막대에 들어가게 되는지 판별할 수 있는 기준이 전부 문제에 적혀 있다. 기준에 따라 각 막대에 들어간 개수를 세주자. 가장 큰 값을 들고 있는 막대가 마지막 막대이니, 전체 막대의 개수를 알 수 있다. 막대 개수와 각 막대의 높이를 알면 문제에 적힌 대로 답을 계산할 수 있다. 2. 편집 거리문제 디스크립션이 많이 엉망이다 ㅠㅠ 다시 문제를 정리하면 다음과 같다. 초기 문자열 S와 최종 문자열 T가 주어진다. 입력 문자열은 처음에 S가 들어있고 출력 문자열은 비어있다. 입력 문자열의 맨 앞 글자를 삭제하고 출력 문자열의 맨 뒤에 글자를 추가하는 다양한 연산들이 주어진다. 연산 후에 입력 문자열은 비어야 하고, 출력 문자열은 T 여야 한다. 복사를 제외한 연산의 개수를 스..

1. The Postman경로에 대한 조건이 없을 때 이 문제는 방향 그래프에서 오일러 회로를 찾는 잘 알려진 문제이다. 오일러 회로는 모든 정점의 indegree와 outdegree가 같으며, 연결되어 있는 그래프라면 항상 존재한다. 이 문제의 그래프가 그러함을 가정하자 (그렇지 않다면 NIE).오일러 회로는 다음과 같은 재귀 함수 Rec(v) 로 선형 시간에 찾을 수 있다. 오일러 회로에 대해서는 복습을 위해 알고리즘만 간략히 적어두고 설명하지는 않겠다. * 정점 v에서 나가는 에지 e를 아무거나 찾고 제거 (사용한 에지들의 인덱스를 전역 변수 등에다 마킹해 놓고, vector에서 pop_back() 하면서 에지를 지워주자) * e의 반대편 끝점이 w라면, Rec(w) 호출 * Rec(w)가 종료되면..

1. 작은 새각각의 쿼리가 그다지 연관성이 없어보이니, 그냥 K가 고정됐다 치고 각 문제를 독립적으로 풀어보자. 결국 쿼리당 O(n)에 해결하면 되니 말이다. O(n^2) 동적 계획법은 다음과 같이 어렵지 않게 할 수 있다. dp(i) = 1번에서 i로 오는 데 필요한 최소의 힘든 점프 수라 하면, 그 전 위치를 j라 했을 때에 대한 식으로 동적 계획법 표를 채울 수 있다. 기본적으로 dp(j)를 가져올 수 있지만, 만약 H_j Ei라는 것은, 어떠한 시간에 Si에 있다가, 그 후에 Ei에 있고, 그 다음에 Si에 다시 돌아와야 한다는 것을 뜻한다. 그렇다면, 최소 Ei -> Si로 한번은 거꾸로 가는 것이 필요하다는 것을 뜻한다. (거꾸로 간다는 것은 돌아온다는 것을 함의한다.) 이들을 [Ei, Si]..

1. 레이저원점을 지나는 직선이 해당 선분을 맞추려면 기울기가 어떠한 수의 구간 사이에 있어야 한다. 그러니 2차원 평면에 직선을 쏴서 선분을 맞춘다고 생각하지 말고, 수직선에 구간이 있는데 점을 몇 개 넣어서 구간들을 덮는다고 생각해보자. 모든 점들이 1사분면 위에 있고 x/y축에 닿지도 않기 때문에, 각 구간은 어떠한 분수와 분수 사이의 폐구간으로 쉽게 표현할 수 있다. 하지만, 더 간단하게 분수가 아닌 정수로 생각해 줄 수도 있다. 각 분수의 정확한 값이 아닌 대소 관계만이 중요하기 때문이다. 고로 좌표 압축을 통해 분수를 적당한 0 - 2n-1 사이의 정수로 바꿀 수 있다. 이제, 0 ~ 2n-1 사이의 정수를 시작점 끝점으로 가지는 n개의 폐구간이 있을 때, k개의 실수를 골라서 최대의 구간을 ..

(5/1 16:53 초판)(5/4 LM 풀이 추가, RST 약간 수정)(8/14 크리님의 생일을 맞아서 다시 풀어보고 있다. YZ 풀이 추가. RST 풀이 약간 추가) 범수형이 검수하러 간 틈을 타서 몰래 껴들어갔다. 팀 이름은 내가 AcornCkiGs14004Team으로 지었다. 하지만 ainta가 지은 기만 팀명에 능욕당했다. 이럴 줄 알았으면 ↑우리보다못하는팀 으로 바꾸고 나올 걸 그랬다...아쉬움 없을 만큼 하고 나왔기 때문에 아주 즐거웠다. 사실 극후반부에 서버가 터져서 PQ 제출에 문제가 있었다. 열심히 제출해도 안 돼서 상당히 짜증났지만, 알고 보니 내 제출이 4시간 59분 59초에 기적적으로 큐에 들어가서 2점을 득점했었다 (...) 그래서 안 짜증났다. 후기는 그냥 좀 재미있던 것만 간략..

1. Fenced In (Platinum)독특한 형태의 그래프에서 최소 스패닝 트리를 구하는 문제이다. 일반적으로 최소 스패닝 트리는 크루스칼 알고리즘을 사용해서 해결하지만, 여기서 그러한 해결 방법을 택하면, 간선의 개수가 너무 커서 시간 제한을 초과하기 때문에, 더 좋은 아이디어가 필요하다.아이디어는 크루스칼 알고리즘과 동일하다. 최소 비용으로 합쳐줄 수 있다면 합쳐주는 식이다. 다만 이 때, 하나 하나 일일이 합쳐준다기 보다는 한꺼번에 한 행 / 열을 합쳐준다는 점을 주목할 필요가 있다. 같은 행 (내지는 열) 에서 좌우로 인접한 셀들을 합치는 비용은 모두 똑같기 때문에 한 번에 생각할 수 있기 때문이다. 한 행과 한 열을 한번에 처리해 주면, O(n+m) 개의 이벤트만이 존재하기 때문에 정렬 한번..

1. Digit DivisionSi = 주어진 숫자의 i자리 prefix를 mod M으로 나눈 나머지라고 하자. Si 배열은 선형 시간에 쉽게 계산할 수 있다.주어진 숫자들을 적당히 나눈 partition이 대충 [i1 + 1, i2] / [i2 + 1, i3] / [i3 + 1, i4] / ... / [i_{k-1} + 1, i_k] 와 같이 생겼다고 하자. 물론 i1 = 0, i_k = N이다. 이 partition이 올바르려면, 모든 1 이상 k 미만의 idx에 대해서 S_{i_{idx + 1}} = S_{i_ idx} * 10 ^ (i_{idx + 1} - i_idx) (mod M)을 만족해야 한다. 이 때, S_{i1} = 0 (mod M)임을 알 수 있다. 고로 S_{i2} = 0 (mod ..

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 번의 상자들은 볼 필..