12월 3일 CERC 17 (GP of Europe) 연습

 

 Opencup GP 하는 날에 팀원이 모두 일정이 있어 못쳤는데, 감도 살릴 겸 해서 연습으로 돌았습니다. GP에서 1등이 -2문제에, "모든 문제가 풀렸지만 만점자는 고사하고 -1도 없는" GP에서 좌셋(?)을 보게 될 줄은 생각도 못했지만, 그래도 좋은 연습이 될 것 같았습니다.

 결론만 말하면 GP에서 2등인데, ITMO한테 패널티로 밀린데다가 ITMO가 B를 7번이나 시도한 것에 비해 저희는 10문제에만 시간을 거의 다 썼기 때문에 약간 아쉬운 결과였던 것 같습니다. 연습에서는 상수가 D를, 도토리가 I를 코딩하는 동안 저에게 거의 1시간 넘게 시간이 있었는데, E의 트리디피 식을 도저히 정리할 수가 없어서 결국 10문제로 마무리했습니다. B도 (정해는 아닌)풀이는 나왔지만, 시간내에 나올지 모르는 알고리즘에 코딩도 1시간어치라 제가 풀 수는 없었습니다.

~1시간: 빠르게 앞쪽 5문제를 밀었습니다. G를 빠르게 생각한 것에 매우 행복했습니다. (G를 3분만에 푼 것이 아니라, 코딩 중간에 J와 스위칭하고 밖에서 풀이 꼬인것을 정리했습니다)

~1시간 반: L을 상수가 간단하게 코딩하는 방법이 없다는 것을 깨닫고 하드코딩을 했고, K는 (아이디어라도 생각하려고) 본 문제를 쉬운 문제로 바꿔서 풀고있었는데 알고보니 그것이 본문제라서 풀었습니다.

~4시간: 이때부터 남은 5문제가 말도 안되는 난이도를 보여주었습니다. D는 풀이가 많이 돌아갔는지 코드 계획이 엄청 길었고, I도 쉬운 풀이가 도저히 생각나지 않아 포기하고 1시간정도 코딩을 했습니다.

~5시간: 도토리가 먼저 I를 맞췄고, D 디버깅시간 동안 C를 도토리가 풀었습니다. 끝나고 정해를 봤는데, CDI 모두 정해보다 어렵거나 느렸던 것 같습니다.

대회때 가장 고생했던 문제 I입니다.

길이 n (n <= 10^5) 짜리 순열 p1, p2, ..., pn이 있습니다. 

{pk | i <= k <= j}가 연속한 자연수를 이루는 구간 [i, j]를 "좋은 구간"이라고 정의할 때,

Q(Q <= 10^5)개의 a <= b 쌍에 대해 i <= a, b <= j인 "좋은 구간" [i, j]중 가장 길이가 짧은 것을 구하면 됩니다.

같은 것이 여러 개 있다면 가장 왼쪽 것을 구해야 합니다.

예제

7

3 1 7 5 6 4 2

3

3 6

7 7

1 3

예제 출력

3 6

7 7

1 7

예제 설명

[3, 6] 구간 내의 숫자 집합은 {4, 5, 6, 7} 으로 좋은 구간입니다.

[7, 7] 구간 내의 숫자 집합은 {2}로 좋은 구간입니다.

[1, 3] 을 포함하는 좋은 구간은 [1, 7]뿐입니다.

---

직전 후기인 Codefestival Exhibition 문제 B는 아직 풀지 못해서 나중에 하겠습니다.