240903 팀 연습 (NERC 2020)

셋: https://codeforces.com/contest/1510 (https://www.acmicpc.net/category/detail/2575)

 

 

대회 중

 

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

 

~0:18 (1솔브)

앞 문제들을 보던 와중 petamingks가 D 풀이를 찾아와 바로 짜러 갔다. 다행히 빠르게 1번에 맞았다.

 

~0:57 (2솔브)

D를 푼 직후 kwoncycle이 G 풀이를 넘기길래 빠르게 짰지만 틀렸다. 그 사이 K 풀이를 낸 petamingks에게 컴퓨터를 넘겼고, 1번 틀리고 맞았다. 그 사이 G는 왜 틀린지도 모르고 시간이 흘렀다. kwoncycle은 이 동안 J를 보러 갔다.

 

~1:28 (3솔브)

kwoncycle과의 대화를 통해 내가 풀이를 잘못 이해했다는 사실을 깨닫고 다시 짜서 맞았다. 이후 kwoncycle은 J, 나는 B, petamingks는 I를 보러 갔다.

 

~2:47 (4솔브)

1시간동안 petamingks는 I의 사풀을 여럿 시도했지만 모두 틀렸고, kwoncycle은 J의 케이스워크에서 헤메고 있었다. 셋 중 가장 많이 풀린 문제는 B였다. B는 내가 얼마 전에 검수한 SUAPC 대회에 있던, 허나 검수하지 않은 사탕 배달이라는 문제와 거의 동일한 문제였다. 검수를 소홀히 한 과거의 나를 탓하며 풀이를 열심히 생각했고, 다행히 그럴듯한 모델링을 떠올릴 수 있었다. 그 사이 kwoncycle이 J의 케이스 워크에서 거의 빠져나왔고, 다행히 맞아 컴퓨터를 잡고 MCMF를 짜기 시작했다.

 

~3:07 (5솔브)

MCMF를 빠르게 짰고 다행히 한 번에 맞았다. 그 사이 petamingks는 I의 진짜 최종 식 정리를 끝냈다고 해 컴퓨터를 넘겨주었다.

 

~3:29 (6솔브)

뭔가 중얼거리더니 I를 냈고, 200개의 테스트 케이스를 모두 통과한 모습을 확인할 수 있었다. 이후 나는 또 선인장 문제인 C, kwoncycle과 petamingks는 E를 잡았다.

 

~5:00 (6솔브)

아쉽게도 문제 오독과 짬 부족으로 C를 해결하지 못했고, E 역시 그럴듯한 풀이가 있었으나 컴퓨터를 잡을 정도가 아니어서 두 문제 모두 해결하지 못하고 끝났다. 대회 종료 후 나와 kwoncycle이 각각 C와 E를 업솔빙했다.

 

문제별 요약

문제	풀이	코딩	비고
A (D5, - )
B (D4, 3:07, +)	leo020630	leo020630	문제에서 요구하는 것은 결국 최소 cost의 path cover와 비슷한 방향으로 생각할 수 있고, 가중치가 있는 이분 매칭으로 잘 모델링한 후 MCMF로 해결할 수 있다.
C (D4, -, upsolved)			선인장에서 단절선만 남긴 뒤 트리에서 어떤 문제를 해결하면 되는데, 문제를 제대로 정의하는 과정이 늦어서 해결하지 못했다. 종료 직후 업솔빙했다.
D (P3, 0:18, +)	petamingks	leo020630	log값을 저장해야 하는 냅색 DP이다. 이를 사용하지 않는 다른 애드혹 풀이도 있다는 것 같다.
E (D4, -, upsolved)			kwoncycle과 petamingks가 N이 작음을 이용한 풀이를 만들었지만 대회 중에는 확신 부족 + 시간 부족으로 짜지 못했다. kwoncycle이 업솔빙했다.
F (R4, - )			스코어보드에 의거해 문제를 읽지 않았다.
G (P4, 1:28, +2)	kwoncycle	leo020630	트리에서 마지막 정점을 정한 후 경로를 잘 구성해주면 된다. 역추적이 필요해 구현이 살짝 길다.
H (R5, - )			스코어보드에 의거해 문제를 읽지 않았다.
I (D5, 3:29, +6)	petamingks	petamingks	난해한 인터랙티브 문제이다. petamingks가 사풀에 빠지는 듯 하더니 정해를 찾아내 해결하였다.
J (D5, 2:47, +1)	kwoncycle	kwoncycle	까다로운 게임 + 케이스 워크 문제이다. kwoncycle이 긴 디버깅 끝에 해결하였다.
K (G4, 0:57, +1)	petamingks	petamingks	간단한 애드혹 문제라고 한다.

 

총평

 

각자 다이아몬드 1개씩을 해결하였지만 후반을 다소 무의미하게 보내 생각보다는 좋지 않은 결과가 되었다.

 

잘한 점 : 각자 문제 풀이 과정에서 다소 말렸지만 잘 해결함

못한 점 : 후반 러쉬가 아쉬웠음, 페널티 관리 조금 실패

 

WF였으면 몇 등? (뇌피셜) : 28/130