2018년 참가 이후 첫 참가다. 작년엔 복학이후 학교 수업 따라가기도 벅차서 icpc와 scpc만 출전했다.
딱히 준비한 것은 아니지만 그래도 정신차리고 풀면 티셔츠는 받지 않을까 하는 생각에 참전한다.
전날 영화보고 잠들어서 거의 12시에 일어나는 바람에 3시간 30분 정도 늦게 시작했지만 예상보다 속도감있게 풀어서 다행이다.
1. Punch Cards
지문 처음부터 읽다가 때려치우고 Input 바로 위 문단만 읽었다.
단순히 n, m 받고 조건에 맞게 출력해주면 되는 언럭키별찍기
2. 3D Printing
얘도 지문이 너무 길어서 읽는데 고생 좀 했는데, 프린터 3개의 잉크량을 입력받고, 모든 프린터에서 1,000,000만큼 출력 가능한지 출력하는 문제다.
말도 안 되게 단순한 문젠데, 전 문제와 달리 Case#: 이후 개행문자 없이 출력해줘야하는 걸 못 보고 개행문자를 계속 출력하는 바람에 3시도 만에 풀었다...
다행히 Sample에서 걸러져서 panelty는 받지 않았다.
3. d100000
그냥 정렬문제다. for loop 하나만 돌리면 끝. 더 할말이 없다.
4. Chain Recations
dfs 한번 돌리면 끝나는 문제다. 카테고리를 나누자면 트리탐색 + 그리디.
처음에는 TreeDp 생각하고 접근했는데, Query를 root(abyss)에서 한 번만 돌리면 되기 때문에 caching이 의미 없고, 그냥 child의 리턴값만 처리해서 뚝딱뚝딱하면 되겠거니 하고 짰다.
Abyss를 root를 보고 dfs를 돌리는데, 현재 위치 x에서 최대값을 얻으려면 x의 자손 중 가장 작은 값에서 현재 위치 x로 오면 최대로 fun을 얻을 수 있다.
그러니, 모든 node의 sum을 구해놓고 여기서 얼마나 더 fun을 올릴 수 있는지 dfs 돌리면서 x와 x의 자손중 최솟값의 차 만큼 sum에 더해주면 끝이다.
트리라는 걸 파악하는데는 1초도 안 걸렸지만 구현하면서 뻘짓을 많이해서 30분정도? 걸렸다.
5. Twisty Little Passages
어려운 Interaction문제는 진짜 접근조차 어렵다.
이걸 보기 시작한게 대회시작 4시간 지나서인데 우리나라에서 한 명도 못 풀었길래 문제만 읽고 생각은 별로 안 해봤다.
Time 제한이나 Mem 제한 보면 휴리스틱하게 갈기는 것 같은데 곧 바로 다른 대회가 있어서 접었다.
2번문제에서 Case#: 출력하는 걸 좀 제대로 보고 제출했으면 45분 컷 가능했는데 급한 마음에 제대로 확인하지 않고 제출하는 바람에 15분이나 딜레이 됐다.
그래도 닉만보면 아는 고인물들하고 시간차이가 얼마 안 나서 만족스럽긴하다.
