이틀 전 KOI 고등부 open contest에 참가해 문제를 풀어봤다. 확실히 코딩실력에는 문제가 많다는 것을 느꼈고, 다양한 구현문제와 자료구조 문제들을 풀어보면 좋겠다는 생각을 했다. 그리고 블로그를 계속 한다면 블로그 포맷?들도 배우면 좋겠다고 생각된다.
1. 줄임말(3 try)
S를 T*N번의 subsequence로 나타낼 수 있겠냐는 문제이다. S와 T의 알파벳을 제한할 이유는 없었던 것 같다.
[풀이] T의 각 알파벳이 몇번째에 등장하는지 벡터로 저장하고, lower_bound질을 하면 된다.
인덱스를 계속 틀려서 3트라이를 박았다.
2. 순서 섞기(2 try)
수열 A가 주어질 때, A의 양 끝점을 하나씩 떼어나가면서 차곡차곡 쌓아 새로운 수열을 만드는 과정을 M번 반복하여 증가수열이 되도록 만들고 싶다. 몇 번이나 반복 해야하는가?
처음에 접근할 때, 최솟값을 찾아 pivot하는 식으로 접근해서 30분정도를 날려먹은 것 같다. 답이 대충 $lg(N!/2^N)~lgN$일 것 같으므로, 이런 관찰이 도움이 되도록 조금 더 생각해주면 수열이 증가, 감소, 증가, 감소,..., 감소(총 m개)라면 그 다음수열은 증가, 감소, 증가.. 감소의 반복이 최소 [m/2]번 있어야 함을 보일 수 있다. 따라서 답은 lg(m)이라는 것을 알 수 있다. 물론 즈홉은 또 인덱스를 실수해서 틀렸다.
3. 화려한 정사각형
5초이므로 스위핑하면서 세그에 맵을 박으면 될거 같아서 읽자마자 안풀었다. 나중에 풀 예정.
4. 경계로봇(3 try)
로봇이 r만큼의 주위를 경계할 수 있을 때, [0, L]을 커버시키려고 한다. 처음 로봇들의 위치가 주어지고, 사람이 0부터 움직이면서 로봇을 이동시킬 수 있다. 이때 가능한 최소 거리를 출력한다.
[풀이] 로봇은 최대 $2Nr$만큼의 길이를 커버할 수 있고 체크해준 뒤 -1을 출력한다.
로봇이 오른쪽으로 무조건 가야하는 길이 X를 구하자.
오른쪽에서부터 X까지는 커버 안된 부분이 있어서는 안되며, 왼쪽에서부터 로봇의 개수가 m개일 때 m번째 로봇의 위치가 (2m+1)r보다 작아야 한다. 이를 이용해 X를 구한다.
로봇이 뒤로 돌아오게 된다면 손해가 발생하므로, $(2i+1)r$로 배치되는 것이 최선이라는 것을 쉽게 증명할 수 있다. 따라서 로봇이 뒤로 돌아오게 되는 부분을 체크해준다.
다시 뒤로 갔다 앞으로 가는 것이 좋은지(뒤로가는 거리의 세배), 아니면 X점을 찍고 그 점까지 되돌아 오는것이 좋은지만 결정해주면 되고, 이는 $O(N)$만에 확인해줄 수 있다.
마찬가지로 인덱스 실수로 3트라이를 박았다. ㄹㅇㅋㅋ
3시간에 1, 2, 4번을 풀었는데, 솔직히 한시간 동안 3번은 아마 못풀었을 것 같다. 그래서 생일 케익을 사러갔다ㅋㅋ. 특히 2번 문제가 재밌었던 셋이었다. 4번은 케이스만 잘 나누면 됐던듯.