구사과

결과본선에 진출했다. 그날 편두통이 있어서 걱정을 많이 했다. 편두통 심하면 아무 것도 못해서... 사실 대회 전에는 졸리고 편두통도 조금 있는거 같아서 거의 본선에 대해 체념 했는데, 다행히도 대회 중에 크게 컨디션 문제가 생기진 않았다. 편두통은 연휴 끝나면 병원 가서 끝을 봐야겠다. 타이레놀도 잘 안들어서 힘들다... 딱히 모난 거 없이 했던 거 같다. A B C중에서 정말 못 풀겠다 싶었던 거는 없었고, 코딩도 그렇게 시간이 오래 걸리지는 않았다. 문제는 뭐 그냥 그냥 괜찮았던 거 같은데, 그래도 얼마 전에 버추얼 돌았던 2016 R3가 훨씬 재밌었다. A. Salient StringsSuffix array가 주어졌을 때 이를 만족하는 string을 복원하는 문제이다. 처음에 잘 모르겠어서 다른 ..

(Mirror Traffic, 2011) 와....

Dropbox 링크

저번에 스타트링크에서 잠깐 강의했을 때 사용했던 자료입니다. 만든 시간이 길지 않아서 자료의 질이 그렇게 좋지는 못하네요. (발표 이후 수정은 없었습니다 ㅠ)일반적인 분할 정복의 사용 예를 떠올리면서, Centroid를 지나는 전체 경로를 한번에 처리하는 것이 도움이 되는 경우가 있는지, 그러한 문제는 어떤 것들이 있는지 생각해 보시는 게 도움이 될 것 같습니다. (사실 이거는 많이 풀어봐야 압니다 ㅋㅋ)추천 문제는 딱히 생각이 안나는데 난이도 순으로 적자면 http://codeforces.com/contest/321/problem/C https://www.acmicpc.net/problem/5820 http://codeforces.com/gym/100570/problem/Fhttp://codeforce..

.. 다 정리할 생각은 없다. 그냥 어젯밤에 풀었던 문제들 정리. https://github.com/koosaga/olympiad/tree/master/POI 에서 ontak10_으로 시작하는 cpp들이 풀이이다. Highways https://www.acmicpc.net/problem/8476 결국 dfs traversal로 나타내면 2차원 평면상에 몇개의 점이 있는지를 세는 문제로 환원할 수 있다. 전형적인 2D Query 문제. main.edu.pl에서 실험해 봤을 때 O(qlg^2n)은 TLE가 났었음. O(n + (m + q)lgn)에 짜야 한다. 요 근래 2D Query는 거의 상식이 되어 가는 것 같다. 잘 해야 한다. Excursion https://www.acmicpc.net/proble..

https://sio2.mimuw.edu.pl/c/wiekuisty_ontak2015/dashboard/ http://zimpha.github.io/2015/09/23/ontak-2015-translation/ 풀 수 있는 거 다 풀어서 종결했습니다. 아인타가 paint 못푼다고 놀려서 올클 도전하기로 했습니다. 올클했습니다. 푼건 이 색깔로 표기합니다. 구현은 https://github.com/koosaga/olympiad/tree/master/POI 에서 ontak15_ 로 시작하는 파일들입니다. Day 1 cie 풀이 설명은 귀찮으니 생략. 요약하자면 왼쪽 오른쪽으로 슥슥 긁으면 풀리는데 구현은 조금 까다롭다. 굉장히 많이 틀렸었는데 이유를 알고 보니 0을 leading zero라고 무시하고 있었다..

ACM ICPC Daejeon Regional 2016에 다녀왔습니다. 당연하지만 고등학생이니 경기하러 간 건 아니고 그냥 놀러 갔습니다. 대학생이 아니라 처음에는 대회를 치르는 사람들이 정말 부러웠지만, 지금 다시 생각해보면 스트레스 안 받고 2층에서 편하게 팝콘뜯으면서 입풀이하고 중계하는게 더 꿀인거 같네요. 아는 얼굴들도 워낙 많았고 재밌는 일도 많아서 오랜만에 정말 즐거운 시간 보낼 수 있었습니다. 특히 zigui님의 코스프레가 정말 인상 깊었습니다. 대전 리저널에 새 역사를 쓰신... 총 12문제가 출제됐는데, 중계석에서 풀면서 느꼈던 점은 어렵고 재미있다는 점이었습니다. 생각에 조금 더 비중이 맞춰졌고, 재미있는 아이디어도 많았던 좋은 세트라고 생각했습니다. 물론 잘 풀었다는 건 아니고, 알고..

(OK Computer, 1997) (쓰고 싶은 건 참 많은데 요즘 너무 바쁘네요. 곧 일이 정리되면 돌아오겠습니다.)

https://granta.com/why-were-post-fact/ As his army blatantly annexed Crimea, Vladimir Putin went on TV and, with a smirk, told the world there were no Russian soldiers in Ukraine. He wasn’t lying so much as saying the truth doesn’t matter. And when Donald Trump makes up facts on a whim, claims that he saw thousands of Muslims in New Jersey cheering the Twin Towers coming down, or that the Mexica..

https://speakerdeck.com/wookayin/fast-fourier-transform-algorithmhttp://cubelover.tistory.com/12 내가 개념을 설명하기에는 위의 링크로도 충분한 것 같아서 따로 설명을 하지는 않겠다. 특히 맨 처음 인용한 ppt 슬라이드가 엄청나게 이해하기가 쉬우니 보면서 따라가는 것이 좋을 것이다. 다만 생각의 흐름 정도를 정리하자면 * 다항식을 표현하는 데 있어서는 sigma(ai * x^i) 형태의 coefficient representation과, {(x1, f(x1)), (x2, f(x2)), .. (xn, f(xn))} 형태의 point-value representation이 있다. lagrange interpolation theore..