구사과

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 ... } 과 같은 형태로 구해진다. 단조 증가한다는 것은 인접한 항들이 모두