티스토리 뷰

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 인터넷 예선과 내년의 대회에서는 더 좋은 성과를 거두면 좋겠습니다.

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

위스키  (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
leejseonal ddforces 개최 후기  (0) 2019.01.07
댓글
댓글쓰기 폼
공지사항
Total
22,275
Today
1
Yesterday
31