구사과

먼저 “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한 느낌이 강했던 문제였고, 풀이의..

(1995)

Github을 통해서 올해 ICPC때 사용했던 팀 노트와, 연습 기록을 공개했다. https://github.com/koosaga/DeobureoMinkyuParty아직 완성된 팀 노트가 아니라, 추가적으로 내용이 찰 때마다 업데이트가 될 예정이다. 팀 연습 역시 하는 대로 결과를 올릴 예정이다.

총평후반부에 너무 루즈했다. 뒷심 + 멘탈이 딸리는 거 같은데 발전이 필요. Short Diary (스포일러 주의)A (0:04)(hyea) x좌표가 같은 경우와 아닌 경우로 나눠풀면 뚝딱이다. B (0:38)(koosaga) 짜증나는 dp인데 결국 어떠한 구간 s, e를 비교할 수 있는 경우의 수를 세면 된다. 각각의 구간에 대해서 [empty][a][b][c][d][...][z] 로 나누는 경우가 27승 정도인데 이건 dp안에 dp를 넣는 느낌으로 하면 된다 (물론 코드가 그렇진 않다..) C (1:23 +1)(alex9801) n

http://autonomousweapons.org/

ScoreboardMy story혜아랑은 옛날부터 팀을 하기로 얘기가 되어 있었다. 2학기 개강 직전에 태평소국밥 (유성 홈플러스 근처에 있고 개꿀맛임) 에서 민규랑 팀을 하기로 최종 합의를 봤다. 예전부터 "지훈이나 민규 둘 중 하나" 라고 얘기를 했고 그래서 팀원을 말하기 참으로 눈치 보이는 상황이었는데 그때 마침 청하 한병을 깐 상황이어서 그냥 얘기해 버렸다. 팀명은 내가 지었고, 괜찮은가에 대해 고민을 아주 많이 했으나 이건 PC보다는 표현의 자유라고 생각해서 확정했다. 적당히 논란이 있어야 좋은 팀명이라는 나의 관종같은 철학이 반영되었다 그 이후 팀 연습은.. 세보니 7번 했다. 다들 바쁘고 시간이 잘 안 겹쳐서 저 정도면 열심히 잡았다고 생각.. 방학 때 최대한 열심히 할 계획이다. 크게 말린..

이 글의 대부분의 내용이 https://koosaga.com/243 에 재작성되었으니, 확인해 보는 것을 추천한다.[2017.07.29 초판][2017.11.10 증명 추가]IOI 2016에 출제된 Aliens 문제의 해법에서는, 굉장히 독특하면서 다양한 문제에 적용될 수 있는 최적화 기법이 나왔다. Aliens 문제와 비슷한 몇 개의 문제를 통해 이 기법을 설명하려 한다. #1. Aliens (IOI 2016 Day2 Problem3) 먼저 이 문제의 최적화 방법을 알기 위해서는 O(nk) 풀이를 알고 있어야 한다. 이 풀이에 대해서는 전명우님의 블로그에 서술되어 있다. 고로 여기서 설명하지 않는다. O(nk) 풀이를 보면, 다음과 같은 특징이 있다.k가 커질수록 답은 항상 감소한다. k에 대한 조건이..

Timeline내 관점에서 본 대회 타임라인은 대충 다음과 같다. 우리 팀은 여느 때처럼 컴퓨터 1대에 인터넷 끊고 팀노트 손으로 치면서 진행했다. * 0분 ~ : 프린터가 고장났어?? (대혼란) * 3분 : 혼란 속에서 A 약간 늦게 accept * 10분 ~ 20분 : J가 풀렸네?? 근데 bitset에 매칭인데?? (대혼란 + 멘탈붕괴) * 20분 ~ 30분 : 딴 걸 아는게 없어서 코딩 시작. 이후 J AC * 30분 ~ 60분 : C 아이디어 나오고 코딩 준비 완료. 혜아 초반부터 BEF 잡다 멘붕. 민규 I 디테일을 정리 * 60분 ~ 75분 : C 코딩하고 예제 맞왜틀. D가 쉽다는 제보 도착 * 75분 ~ 90분 : 민규 D 코딩 * 90분 ~ 92분 : C 몇글자 고치고 AC * 93분 ..