240904 팀 연습 (The 3rd Universal Cup. Stage 7: Warsaw)

셋: https://contest.ucup.ac/contest/1774

 

 

대회 중

 

petamingks가 앞, 내가 가운데, kwoncycle이 뒤를 보고 시작했다.

 

~0:17 (4솔브)

가장 쉬운 문제 중 하나인 J를 kwoncycle이 빠르게 풀었다. 나는 그 동안 G를 보았는데, 최근 같았으면 자신감이 사라져 petamingks에게 넘겼겠지만 팀 연습이 잘 되고 있던 찰나라 그냥 믿음을 가지고 1분만에 짜서 맞았다. 내 기억이 맞다면 세컨드 솔브였는데, 조금 아쉬웠다. 이후 kwoncycle이 M을 풀고 나는 petamingks에게 D 풀이를 넘겨받아 짜서 맞았다. 네 문제가 모두 골드급이긴 했지만 굉장히 좋은 스타트를 했고, 그 결과는..

 

세상의 꼭대기에서 1557을 외치다

 

괴수 집합소 유니버셜 컵에서 잠시나마 1등을 차지할 수 있었다.

 

 

~0:53 (6솔브)

이후 나는 B, kwoncycle과 petamingks는 L과 F의 풀이를 의논하였다. B도 어렵지 않은 문제였기에 빠르게 코딩했고, 1번 틀린 후 맞았다. L 역시 B를 틀린 사이 코딩을 어느정도 해 두었기에 빠르게 AC를 받을 수 있었다.  이때의 스코어보드는 아래와 같다.

 

 

~1:35 (7솔브)

둘이 F를 푸는 동안 나는 안 풀린 문제들을 모두 읽었다. H는 기하 케이스 워크 문제여서 kwoncycle에게 주고 나는 트리 문제인 K에서 몇 가지 관찰을 해 두었다. F는 kwoncycle과 petamingks가 무한 TL 끝에 언어를 파이썬에서 C++로 바꾸고 해결하였다.

 

~3:49 (8솔브)

이후에는 petamingks가 E 풀이를 냈다. 맞은 사람이 워낙 없고 시간복잡도도 너무 넉넉해서 틀린다는 생각이었지만, 컴퓨터가 비어 있어 일단 짜고 틀렸다. 나와 petamingks 모두 풀이의 논리적 결점을 찾아내기 불가능하다고 생각했지만 스코어보드를 믿고 우선 다른 문제로 떠났다. 컴퓨터는 kwoncycle의 H로 넘어갔고, 나는 K / petamingks는 A를 계속 보았다.

 

이후 H 코딩이 완성되었지만 WA를 받았고, 나와 petamingks 모두 별 진전이 없는 상태였다. 일단 petamingks에게 A 풀이를 알아낸 만큼이라도 설명해달라고 했는데, 열심히 말하던 도중 갑자기 풀이를 깨달았다고 했다. 꽤 까다로운 DP라 이해에 시간이 조금 걸렸지만 어찌저찌 코딩을 끝낼 수 있었고, 다행히 1번에 AC를 받았다.

 

~5:00 (8솔브)

남은 시간 동안은 kwoncycle이 H를 계속 고쳤으나 맞왜틀에서 나오지 못했고, 나와 petamingks는 K 사풀을 짰으나 될 리가 없었다. 끝나고 확인하니 H는 부호를 조금 고치면 맞았다고 한다.

 

문제별 요약

티어는 추측입니다.

문제	풀이	코딩	비고
A (D4, 3:49, +)	petamingks	leo020630	어려운 관찰이 여럿 필요한 DP 문제이다. 한 번에 사용할 수 있는 비용이 작음을 이용해 모든 경우를 적은 상태로 표현할 수 있음이 핵심이다.
B (P5, 0:45, +1)	leo020630	leo020630	그리디하게 생각하면 어렵지 않게 해결할 수 있다.
C (?, - )			스코어보드에 의거해 문제를 읽지 않았다.
D (G3, 0:17, +)	petamingks	leo020630	전형적인 골드 문제이다.
E (D2, -2)			굉장히 그럴듯한 다익스트라 풀이를 만들 수 있지만, 엄청난 반례가 존재한다. 정해는 경로를 그으면 평면이 나뉘어짐을 이용한 min cut이라고 한다.
F (D4, 1:35, +7)	petamingks	kwoncycle	해싱에 대한 이해도가 필요한 문제라고 한다.
G (G4, 0:06, +)	leo020630	leo020630	남기는 줄을 결정한다고 생각하면 각 행의 최솟값 중 최댓값이 답임을 알 수 있다.
H (P1, -8, upsolved)	kwoncycle	kwoncycle	까다로운 기하 케이스워크 문제이다. 코너 케이스 처리 조금이 부족해 대회 중에 해결하지는 못했다.
I (?, - )			스코어보드에 의거해 문제를 읽지 않았다.
J (G5, 0:05, +)	kwoncycle	kwoncycle	문제를 읽지 않았다.
K (D5, -5)			관찰을 좀 하면 문제를 변형할 수 있지만 마무리가 되지 않아 해결하지 못했다.
L (P3, 0:53, +1)	petamingks	kwoncycle	입력이 랜덤함을 잘 이용하는 문제라고 한다.
M (G2, 0:13, +)	kwoncycle	kwoncycle	문제를 읽지 않았다.

 

총평

 

초반을 역대급으로 잘 보냈으나 뒷심이 조금 부족한 점이 아쉬웠다. 골드 문제들은 어차피 WF에 잘 나오지 않기 때문에 크게 만족할 만한 점은 아닌 것 같다.

 

잘한 점 : 전반적인 문제 해결 속도

못한 점 : 풀어야 하는 문제인 K 풀이를 내지 못함

 

WF였으면 몇 등? (뇌피셜) : 26/130 (H 맞으면 17/130)