구사과

먼저 “Alice가 답을 TT 이상으로 하는 게임을 진행할 수 있는가, 없는가?” 라는 변형된 문제를 풀어보자. 변형된 문제를 빠른 시간 안에 풀 수 있다면, 이분 탐색을 통해서 Alice가 진행할 수 있는 게임 중 TT가 가장 큰 것을 찾을 수 있고, 이것이 Alice가 얻을 수 있는 최댓값이기 때문이다.이후부터는 문제를 그래프로 변형해서 해결한다. ∣Au−Av∣ 3이고 짝수인 경우에는, Bob이 정점을 지운다. ⌈n/2⌉=⌈(n−1)/2⌉\lceil n/2 \rceil = \lceil (n-1)/2 \rceil 이기 때문에 어떤 정점을 지우더라도 귀납 가정을 만족해서 Alice가 이긴다.n>3이고 홀수인 경우에는, Alice가 이번 턴을 진행한다. 만약에 최대 클리크의 크기가 ⌈n/2⌉\lceil n..

방향 그래프의 Dominator Tree의 유래, 개념에 대해서 짤막한 글을 써보았습니다.Dominator Tree를 빠르게 구하는 알고리즘에 대한 언급은 없습니다. Dominator Tree를 빠르게 구하는 알고리즘은, 그 증명 방법과 내용이 상당히 길고 복잡하기 때문입니다. 개인적인 생각으로는 그 부분까지 이해할 필요는 없고, 구현체만 팀노트에 넣어도 문제 해결에 충분하다고 생각합니다.

온사이트 대회가 끝나고 후기를 쓴 경험이 많지 않다. 쓸 내용이 많은 것도 있고, 대회가 끝난 이후에는 항상 일정이 바빴기 때문이기도 하다. 이번에도 예외는 아니지만, 집에 가는 기차에서 짧게나마 경험담과 느낀 점을 적어보려고 한다. 는 개뿔… 글이 길어져서 한 달 뒤 태국 리저널 가는 비행기에서까지 후기를 쓰고 있다. 그리고 크리스마스에 마감. Qualification 상식적으로 앳코더 대회에서 세계 20등을 할 가능성이 당연히 없다고 생각해서 Qual A는 그냥 걸렀다 (아마 그 날 어디 나갔던 것 같다). Qual B도 비슷한 생각이었지만, 바쁘지 않고 앳코더 대회가 있으면 쳐야지. 그래서 쳤다. D를 열고 시작했는데, 상당히 어려웠던 문제였다. 굉장히 ad-hoc한 느낌이 강했던 문제였고, 풀이의..