티스토리 뷰


8.17에 열린 SCPC 본선에 참가했다. 작년이랑 같은 장소에서 했고 올해는 키보드, 마우스, 장패드 기타 등등을 줬다. 



키보드 예쁘다 ㅋㅋㅋㅋㅋ 

이것 저것 줏어먹으면서 구경하다가 1시 반부터 본선을 시작했다.


4시간 동안 짱구를 열심히 굴려서 1, 2번을 풀고 3번 서브테케를 긁었다.



1번은 SCPC 2017 문제를 통틀어서 가장 쉬운문제가 아니었나 싶다.

문자열에서 모음이 순서대로 나오는 최단길이를 구하고 그 중 가장 빠른 위치를 출력하는 문제였다.

그냥 O(N^2)으로 구하면 된다. 128 명 본선에 참가한 것으로 아는데 125명이 풀었다.


2번은 2개의 볼록다각형이 있을 때 두 볼록 다각형간의 가장 짧은 거리를 구하는 문제이다.

A 볼록다각형의 모든 점에서 B 볼록다각형의 모든 선분에 대해서 점과 선분의 최단거리(삼분검색)를 구하는 방법으로 구현하면

O(N^2logN)이다. 위 방법은 섭테 1을 통과 할 수 있다.

A 볼록다각형의 한 점과 가장 가까운 B 볼록다각형의 선분을 알고 있으면 A 볼록 다각형의 다음 점은 현재 알고있는 선분에서 시계 또는 반시계 방향으로 이동하면서 가장 가까운 선분을 찾으면 된다. 따라서 O(NlogN) 까지 줄일수 있고 섭테 2를 통과 할 수 있다.

점과 선분의 최단거리를 삼분검색으로 구하지 않고 다양한 기하적 방법을 이용해 O(1)에 구하면 O(N)이고 섭테 3을 통과 할 수 있다.

36명 풀었다.


3번은 문제 설명은 귀찮으므로 생략하고, O(N^2) 방법으로 쉽게 서브테케 2번을 해결하고 143점을 얻을 수 있다.

대회중에는 1시간 반동안 생각해 봤지만 파라매트릭 서치까지 접근하고 더이상 진전이 없어 4번 섭테를 읽었다.

O(Nlog^2N) 풀이는 파라매트릭 서치로 K년을 정하고 해당 K년에 대해서 우주선1이 갈 수 있는 범위를 정사각형(주대각선이 x축, y축과 평행인)으로 표현했을 때 우주선2가 정사각형들중 하나라도 포함되면 가능이다. 이 판별을 플레인 스위핑으로 할 수 있다. y=x+k 의 y-x 를 x좌표로 y=-x+k 의 y+x 를 y좌표로 생각하고 좌표 압축후에 x좌표로 소팅하고 y좌표에 대해서 bit로 구간 업데이트하면서 우주선2에 해당하는 점에 대해 쿼리 찍으면 정사각형 내부인지 판별가능하다. 

39명 풀었다.

(왜 플레인 스위핑을 생각 못했을까 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ 아쉽당)  


4번은 갓문제이므로 생략한다. 

처음에 1번 서브테케를 문제를 대충 읽고 그냥 비트마스크 bfs인줄 알고 돌렸다가 틀렸다. 단순히 꺼지고 켜진게 아니라 학생번호가 존재했다.

사실 2번 서브테케가 점수가 더 낮고 더 쉬운 테케였다. 트리에서는 0을 루트로 잡고 0을 리프까지 내리는 방법만 가능하다. 그리고 해당 방법이 최단이다. 모두 구하면 된다.

나머지는 잘 모르겠다. 2명 풀었다.


총평)

1번 너무 쉬웠다. 변별력의 의미조차도 없는 문제였다. 물론 출력을 잘 못해서 한번 틀렸다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 평균 점수는 내가 깍아먹은듯 하다.


2번 기하문제치고는 전형적인 문제였던것 같다. 큰 관찰도 필요없고 기하를 평소에 풀어보았냐? 이런 느낌이었다.


3번 45도 기울어진 정사각형에 대한 플레인 스위핑 + 파라매트릭 서치 문제로 입상하려면 이정도는 풀어야한다는 느낌이다.


4번 초상위권 변별력을 위한 갓문제


입상컷은 650 ~ 680 정도로 예상한다.

아쉽게 입상하지 못했다. ㅠㅠㅠㅠㅠㅠㅠ 2, 3번 점수 배점탓이 있을것 같다. ㅠㅠ

많은 실수도 없었고 평범하게 잘했는데 잘하는사람 너무 많다. 외국인의 외침도 있었다!

더 잘해야겠다. 내년 마지막 scpc까지 힘내자~


PS) 끝나고 홍준님이랑 유카리코님이랑 저녁먹으면서 이런저런 이야기들을 했다. 갓홍준님이 '킹갓소고기살살녹는다~'를 사주셔서 정말 맛있게 먹었다. 구우우우우우우우우우우웃~~~

댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함