2023 IOI 멘토교육 5주차

CEOI 2016을 돌았다.

0:00 ~ 1:47

1번과 2번을 읽었다. 1번은 나이브가 쉽고 풀태는 바로 안 떠올라서 2번을 읽고 풀었다. 나이브랑 풀태 모두 자꾸 틀려서 시간을 많이 날렸다. 처음에 dnc opt 풀이랑 덱dp 풀이를 내서 둘다 짰는데 둘다 틀린 풀이였다. 100점 받으려면 대충 비트스트링 들고 다니면서 적당히 dp 돌려주면 O(NTS)에 문제를 해결할 수 있다.

 

1:47 ~ 3:34

3번을 읽었다. input 노드 루트개 / output 노드 루트개 연결하는 노드들을 만들고 연결하면 47점을 받을 수 있다. 100점을 받으려면 이를 다중으로 해주면 된다. i번째 층의 노드는 input 노드 P^(i/k)개, output 노드 P^((k-i)/k)개를 연결하는 노드라고 놓으면 추가 노드 개수 (k-1) * N^2 / P개, 간선 개수 k * N^2 * P^((1-k)/k) 정도가 나오고, k = 5로 두면 넉넉하다. 간선 만드는게 생각보다 까다로운데, 그냥 나이브하게 N^2개의 경로를 모두 보면서 간선을 다 추가해버리면 매우 간단하게 구현할 수 있다. 이 문제도 자꾸 구현미스가 나서 시간을 많이 날렸다.

3:34 ~ 4:48

1번을 고민했다. 제곱 나이브를 최적화할 수 있는 형태로 변형하려고 시도했다. 현재 i개를 결정했다고 하고, 스택에 매칭되지 않은 문자 st[0], st[1], ..., st[k-1]가 있다고 하자. (st[k-1]이 top이다.) j = N으로 두고 새로운 스택을 들고 그리디를 하는데, st2[0] = st[0], st[1] = st[1], ..., st2[k-1] = st[k-1]이 되도록 그리디를 돌렸다고 하자. a[j] = st2[k-1]인 상태에서 멈췄다고 가정하면, a[(i+1)...(j-1)]이 올바른 괄호문자열인 것이 현재 답이 존재할 필요충분조건이다. j와 st2를 관리하는 것과 괄호문자열 판별은 적당한 dp / 스파스테이블 전처리를 통해 최적화할 수 있다. 따라서, 맨 앞부터 (를 시도해보고 안 되면 )를 넣는 방식으로 답을 구하면 된다.