한국 시간으로 7월 17일 오전 8시부터 24시간 동안 진행되었으며, 총 세 문제가 나왔습니다. 각 문제당 small, large 데이터가 제공되며, small 데이터를 맞추면 5점, large 데이터를 맞추면 20점을 주고, 25점 이상의 점수를 획득하면 다음 round에 참가할 수 있는 대회입니다.
A. Saving the Universe
검색엔진 목록(s개, 배열 S[0..s-1])과 검색어 목록(q개, 배열 Q[0..q-1])이 주어지는데, 검색엔진 이름과 동일한 검색어를 검색엔진에 집어넣으면 안되는 상황이다. 한 검색엔진에 순서대로 검색어를 넣다가 다른 검색엔진으로 옮겨서 검색어를 넣는 방식으로 검색어를 집어넣을때, 검색엔진을 옮기는 최소횟수를 구하시오. 라는 식의 문제입니다.

1. 얼핏 봐도 greedy가 통할 것 같은 문제입니다. 임의의 i에 대해서 A[i] 는 i번째 검색어부터 끝까지 진행했을때 최적해라고 생각합시다. A[0] >= A[1] >= A[2] >= A[3] >= ... >= A[q-1]입니다. 즉 A는 nonincreasing sequence이다. ... [1] 이제 A[0]을 구하자고 생각해봅시다. 검색엔진 중 임의의 하나를 뽑아 j라고 합시다. 그 j로 검색할 수 있는 최대한을 Bj라고 합시다. 그럼 A[0] <= A[Bj+1] + 1 이라고 할 수 있습니다. 가능한 j가 여러가지 있는데, 그중 가장 높은 Bj를 뽑아낼 수 있는 j를 선택하는게 최적해가 됩니다.(왜냐하면 A는 nonincreasing이니까) 그러고 나면 A[Bj+1]을 구하는 문제로 줄어드는데 이것도 A[0]을 구하는 것과 마찬가지로 풀 수 있습니다. 즉, 우리는 0에서 j를 찾고, Bj+1에서 새로운 j를 찾고, 새로운 Bj+1에서 또 새로운 j를 찾고... 를 반복하면 됩니다.
2. i에서 j를 찾는 방법 j를 찾는것도 여러 가지 방법이 가능한데, 간단한 방법을 소개하겠습니다. Q[i..k] 를 집합 { Q[i], Q[i+1], ... ,Q[k] } 라고 합시다. 이때 |Q[i..k]| (Q[i..k]의 크기)는 nondecreasing입니다. ... [2] Q[i..k-1] >= Q[i..k] - 1 입니다. ... [3] |Q[i..k]| = s이면 Ba >= k인 a는 존재하지 않습니다.(왜냐하면 Q[i..k]에 모든 검색엔진들이 포함되기 때문에) k를 하나씩 늘려가면서 Q[i..k]를 구하면, |Q[i..k-1]|=s-1이면서 |Q[i..k]|=s인 지점에서 S[a] == Q[k]인 a를 j로 선택하면, 그때의 Bj는 k-1이 됩니다. 그러나 그 외의 것들을 j로 선택하는 경우에는 Bj가 k-1보다 작아지기 때문에, a를 j로 선택하는 것이 최적해가 됩니다.
3. 그러니까 결국... Q[i..k]에 해당하는 것을 set 혹은 map으로 잡고, 그 size가 s-1에서 s로 되는 순간마다 j를 선택해서 문제를 줄여나가면 됩니다. [code] #include #include #include