KOI 고등부 풀기 (7년을 7일에) 2일차

시험이 끝나고 재활하는김에 원래 풀려고 했던 KOI를 모아놓고 쭉 돌아보기로 하였다. KOI 2013 ~ 2019년도의 문제를 모두 모아놓았다.

문제 리스트는 아래와 같다.

•  A - 사냥꾼
•  B - 막대기
•  C - 전봇대
•  D - 수족관 3
•  E - 버스 노선
•  F - 관중석
•  G - 동전 게임
•  H - 구간 성분
•  I - 매트
•  J - 여왕벌
•  K - 리조트
•  L - 주유소
•  M - 트리
•  N - 먼 별
•  O - 물통
•  P - 문명
•  Q - 요리 강좌
•  R - 조개 줍기
•  S - 화살표 그리기
•  T - XCorr
•  U - 조화로운 행렬
•  V - 족보
•  W - 괄호
•  X - 검은 돌
•  Y - 고압선

2일차 결과

요즘 계속 바쁘기는 했지만 그래도 E,F,M 을 새로 풀었다. 

버스노선 문제는 아침에 일어나자마자 생각해서 그런지 좀 생각을 했다. 완벽히 포함되는 갯수를 세는 것인데 항목이 3개도 아니고 2개였다. 하위호환이라서 못풀리가 없지만... 세그를 쓰기 싫으니 생각보다 아이디어 생각이 잘 안났다. 그래도 조금만 고민하니 바로 생각나서 아침에 일어나자마자 코딩했다.
버스노선 풀이 (준비중)

관중석문제는 딱히 말할 것도 없다. 
관중석 풀이 (준비중)

트리에 몇시간을 쏟았는지를 모르겠다. 대회였으면 크게 뇌절 박고 망했을 것 같다. 위에 11틀이 이를 증명해 주고 있다. 다른 풀이도 있겠지만, 최근 연습 중인 알고리즘이 딱 생각나서 바로 사용을 했다. 일단 나의 풀이 중에는 lca가 사용되어지는데, sparse table을 채우는 함수를 호출을 안하고 있었다.... 그와중에 예제는 다 맞고 있었다. 이래서 좋은 예제, 반례를 찾는 것도 굉장히 중요한 것 같다. 최근에 실수를 많이 줄였지만, 더 줄여나가야 한다. 앞으로 대회의 기회는 몇 번 없고, 그 대회에서 "실수"라는 변명은 더 이상 통하지 않는다. 굉장히 실망했고 아쉬웠던 문제
트리 풀이 (준비중)

원래는 koi 1년치의 풀 수 있는 문제를 모두 풀면 그 때마다 그 년도의 풀이글을 적고 링크를 걸려고 했는데, 그냥 풀이글을 바로바로 써놔야 될 것 같다. 물론 년도별로 글을 쓸 것이고 아직 못 푼 문제는 풀이 준비중이라고 해놓으면 될 듯하다. 내일부터는 진짜 너무 할게 많아서 잠시 쉬어야 할 수도 있다. 그래도 다이아는 좀 풀어야 할텐데 말이다...