구사과

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=639&page=show_problem&problem=4917 설명이 개판인 점은 양해 부탁한다 (풀이 쓸 시간이 없음.. ㅠㅠ) 어떠한 시간에 대해서 겹치는 구간이 100개인데, 이는 임의의 interval i 에 대해서, sj < si이며 자신과 교차하는 interval이 100개 이하라는 것으로 해석할 수 있고, 고로 모든 교차 쌍의 개수가 100N개 이하라는 결론으로 귀결된다. 요트를 모두 시작점 순으로 정렬하자. 만약에 요트가 단 하나라면, 간단한 dynamic programming을 통해서 O(N)에 해결할 수 있다. 문제는 요트가 두개라는 ..

http://main.edu.pl/en/archive/ceoi/2010/pin 편의상 입력되는 문자열을 [0, 35] 사이의 정수 4개라고 생각하자. D[A][B][C][D] 을 (0

(5.14 첫 작성) 대회때 100 / 26 / 100점을 받았다.http://apio2016.org/results/ Problem 1. Boat처음 봤을 때 어려워 보이지는 않았고, 어쨌든 대회 시간 안에 풀수 있을 것이라 생각했다. 실제로도 아주 어려운 문제는 아니었지만, 완전히 잘못된 풀이에 낚여서 1시간 이상을 허비한 게 아직도 아깝다. 그걸로 코딩까지 했으니 원.. 틀린 아이디어를 완전히 버리고, subtask를 읽어나가면서 차근 차근 다시 생각하니, 이 때는 쉽게 풀렸다. 먼저 편의상 interval을 [ai, bi+1) 형태로 처리하자. 이러한 형태의 문제에서 가장 큰 걸림돌은 구간의 길이가 크다는 것이니, 어떠한 긴 구간을 빠르게 처리할 수 있는 방법을 고민해봐야 한다. 좌표 압축을 통해서..