티스토리 뷰

ICPC 인터넷 예선을 앞둔 팀연습겸 해서 KAIST 교내 ICPC 모의대회에 참가했습니다. 저희 팀 명은 jungICPCmangja였고, 팀원은 ICPC 팀원과 같이 김정우(항공우주공학과)님과 박수빈(새내기과정학부)님이었습니다.

저희 팀은 A, B, D, E, G, 이렇게 총 5개의 문제를 해결하였고, H번은 아쉽게 해결하지 못했습니다.

아래는 프리즈가 풀리기 전의 스코어보드의 사진입니다.

 

해결한 문제

저희 팀이 해결한 문제 중 A, G는 박수빈님이, B, D, E는 제가 해결하였습니다. 제가 해결한 문제에 대한 풀이를 간략히 적습니다.

B. And the Winner Is... Ourselves!

그리디하게 빠른 시간 안에 해결할 수 있는 문제부터 해결해주면 됩니다.

D. Capital

문제의 제한이 작으므로 모든 도시에 대해 capital이 될 수 있는지의 여부를 확인해주면 됩니다.

어떤 도시가 capital이 될 수 있는지 확인하는 것은 BFS를 통해 다른 도시 까지의 거리를 구한 후, 각 간선을 살펴보며 capital이 될 수 있는지의 여부를 확인해보면 됩니다.

E. Gosu 2

길이 $\lfloor \log_2 N \rfloor +1$인 chain의 존재성을 수학적 귀납법으로 증명할 수 있습니다.

이 증명은 건설적인 증명으로, 그대로 코드로 옮길 수 있고, $\mathcal{O}(N^2 \log N)$ 알고리즘을 얻게 됩니다.

해결하지 못한 문제

저희 팀이 해결하지 못한 문제는 C, F, H가 있습니다. 이 중, 제가 고민하던 문제는 H번입니다.

H번 문제의 경우, 홀수/짝수로 나누어 A의 "작은" 절반과 B의 "큰" 절반이 "대응"되어야 한다는 사실을 이용하면 해결할 수 있습니다.

제가 이 관찰을 했지만, 이 알고리즘을 잘못 코딩하여 틀렸고, 틀린 관찰로 간주하고 코드를 고치지 않아서 해결하지 못했습니다.

저희 수준에서 해결할 수 있는 문제는 H를 제외하고 전부 해결한 것 같지만, 아쉬움이 남았습니다. 내일 있는 ICPC 인터넷 예선과 내년의 대회에서는 더 좋은 성과를 거두면 좋겠습니다.

'일상' 카테고리의 다른 글

연인 관계의 수에 대한 짧은 이야기  (1) 2019.10.25
위스키  (0) 2019.10.21
KAIST 9th ICPC Mock Competition 참가 후기  (0) 2019.10.04
UCPC 2019 온라인 예선 후기  (0) 2019.07.29
UCPC 2018 연습 후기  (0) 2019.07.27
컴알못이 첫 데스크탑 맞춘 후기  (0) 2019.01.13
댓글
댓글쓰기 폼