구사과

이 글의 대부분의 내용이 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분 ..

총평I를 못풀어서 어쩌나 했는데 그거 빼고 다 풀어서 다행이다. 말린거 같았는데 생각보다 나쁘지 않았음 Short Diary (스포일러 주의) A (0:34 +1)(hyea) 처음과 끝 조건을 잘 보자, 실수를 쓰면 풀리는 문제지만 BigInteger를 쓰는게 안정적인것 같다 B (4:09)(alex9801) Yet another ant problem. 개미에 색깔이 추가되었지만, 어렵지 않게 풀 수 있다.(koosaga) 기본적으로 원에 올려놓은 개미 문제. 일반적인 개미 문제랑 관찰이 크게 다르지 않다. 사실 원이라서 엄청 헷갈렸는데 민규가 많이 도와줬다. C (1:44)(hyea) 적당한 관찰을 하면 풀 수 있는 문제이다. 숫자가 작아서 DB를 만들어도 된다. D (2:47 +3)(hyea) 수식을..