[IOI2011 Day2] Elephants 해법
문제: http://www.ioi2011.or.th/hsc/tasks/KOR/elephants.pdf대회 당시 이 문제에 상당히 많은 시간을 투자했다. 시간제한이 9초라는 것을 간과하고 단지 N 제한이 크다는 이유 만으로 해법이 $O(N lg N)$ 꼴로 나올 것이라 확신했었다. 부분 점수를 받기 위해 $O(N\sqrt{N})$ 꼴의 방법도 생각해보았지만, 실패했었다.대회 끝나고 나오자마자 당시 조교로 있었던 권순일 형의 짧은 말로..
IOI/IOI2011
2013.07.24 01:52
[IOI2011 Day2] Crocodile 해법
문제: http://www.ioi2011.or.th/hsc/tasks/KOR/crocodile.pdf우선, 0번 방에서 탈출 방에서 가는 것이 아닌, 탈출방에서 각 방으로 가는 방향으로 뒤집어 생각해야한다. $$D[i] = 악어문지기가\ 최선을\ 다\ 할때,\ 임의의\ 탈출방에서\ i번\ 방으로\ 오는\ 최소\ 시간$$D[i] 를 위와 같이 정의하자. D[i]는 i번 방으로 올 수 있는 방들 중에 D[j]+(j번 방에서 i번 방으로..
IOI/IOI2011
2013.07.24 01:30
[IOI2011 Day1] Garden 해법
문제: http://www.ioi2011.or.th/hsc/tasks/KOR/garden.pdf 대회 때, 문제가 너무 어려워 보여 별다른 도전을 하지 못한 채 49점을 받았다. 최근에 문제를 다시 풀어보았을 때, 노가다 문제임을 알 수 있었고, 까다로운 코딩 끝에 만점을 받을 수 있었다. 대회 때 문제를 풀지 못한 것에 대한 아쉬움이 커졌다. 이 문제는 69점을 받는 방법이 딱히 생각 나지 않는다. 다만, 코딩할 때 배열 대신 vector..
IOI/IOI2011
2013.07.23 03:23
공지사항
최근에 올라온 글
- Total
- 123,707
- Today
- 3
- Yesterday
- 87
링크
TAG
- Splay Tree
- USACO
- majority
- ioi
- BOI 2009
- moore
- z-trening
- Greedy Method
- Algorithm
- Divide & Conquer
- BOI 2001
- IOI2011
- optimization
- Boyer
- Dijkstra
- Boyer-Moore Majority Vote Algorithm
- idea
- vote
- IOI2014
- TRIE
- IOI2012
- Parametric Search
- IOI2013
- HackerRank
- BOI
- Dynamic Pramming
- Tree
- Knuth Optimization
- Segment tree
- dynamic programming