220701 팀 연습 (SUAPC 2021s)

셋은 SUAPC 2021s을 사용하였으며, 지난 주와 마찬가지로 3시간 3컴으로 진행하였다. 오전에는 모비스 대회도 쳤지만, 민형사상 처벌이 무섭기 때문에 생략하도록 하겠다.

 

내가 뒤, slah007 선배가 앞, qjatn0120 선배가 가운데를 보고 시작했다.

 

~0:09

뒤 네 문제를 스윽 봤을 때, 쉬워보이는 문제가 없었다. 뭘 잡을지 고민하던 중 A와 F의 AC가 나왔다.

 

~0:12

이후 slah007 선배가 D가 쉽다 해 가서 풀었다. 세팅이 지난 셋에 있던 문제와 같아 빨리 풀이가 나왔던 것 같다.

 

~0:23

이후 뒤 문제들 중 그나마 쉬운 K를 잡았다. 쉬운 문제는 아니었지만, 앳코더에서 본 적이 있었던 문제라서 풀이를 빨리 찾을 수 있었다. 바로 짜서 AC

 

~0:35

이후 C와 E의 AC가 나왔다. 나는 qjatn0120 선배가 쉽다 한 H를 잡았다.

 

~0:44

H를 그냥 짜면 될 것 같길래 짰더니 틀려서 qjatn0120 선배에게 넘기고 다시 뒤로 돌아와 I를 잡았다. qjatn0120 선배는 H를 빠르게 미신 후 L과의 사투를 선언했다.

 

~1:27

slah007-G, leo020630-I, qjatn0120-L을 잡은 후 꽤 오랜 시간이 지나 G의 AC가 나왔다.

 

~1:56

이후 30분 쯤 있다가 I를 맞았다. B는 선인장에 자신이 없어 패스하고, 플로우로 보이는 J를 slah007 선배와 같이 보았다.

 

~2:38

이후 J 풀이를 찾아 짜서 냈다. MCMF를 바로 짤 자신은 없어서 팀노트라 치고 코드를 긁어왔다. 역방향 간선 비용 처리를 해주지 않아 한 번 틀리고 AC.

 

~4:20

이후 긴 시간동안 L과의 사투가 있었다. qjatn0120 선배가 짠 10000B짜리 코드가 시간초과를 뱉었다. 이유는 보기 쉽게 짜느라 쿼리를 중복해서 여러번 날린 까닭인 것 같았다. 어떻게 비벼보려 했지만 실패했고, 결국 모두 밀고 다시 짠 후 AC를 받을 수 있었다. 나도 심심해서 같이 짰다.

 

문제별 요약

A (G5, solved by slah007) : 문제를 읽지 않았다.

B (D4, Not solved) : 선인장 무서웡

C (G2, solved by slah007) : 문제를 읽지 않았다.

D (G5, solved by leo0206300) : 간단한 확통 지식이 있다면 해결할 수 있을 것이다.

E (G1, solved by qjatn0120) : 문제를 읽지 않았다.

F (B1, solved by qjatn0120) : 문제를 읽지 않았다.

G (P1, solved by slah007) :문제를 읽지 않았다.

H (G2, solved by qjatn0120) : 그리디하게 처리해주면 되는데, set 이분탐색이나 투 포인터로 하면 된다고 한다.

I (P1, solved by leo020630) : 문제에서 요구하는 기준을 잘 이해한 후, 한 자리씩 잘 처리해주면 된다. 이렇게 말하니 별 것 없어보이지만, 기준도 상당히 어렵고 구현도 복잡하기 때문에 시간이 오래 걸렸다. 다행인지는 모르겠지만 예제는 매우 친절해 예제만 맞으면 기쁜 마음으로 낼 수 있다.

J (P1, solved by leo020630) : 문제에서 요구하는 기준과 각 정점의 indegree와 outdegree가 모두 1임은 동치이다. 따라서, 이를 이분 그래프에서의 매칭으로 치환할 수 있다. 여기서 MCMF를 하면 해결

K (P5, solved by leo020630) : pair 순으로 정렬해준 후 현재 쓸 수 있는 버스 중 가장 좋은 버스를 선택해주는 것을 그리디하게 처리해주면 된다. multiset을 쓰면 쉽다.

L (D4, solved by qjatn0120, leo020630) : 금광 세그를 안다면 풀이는 어렵지 않게 찾을 수 있을 것이다. 하지만, 경우가 너무나도 많고 구현도 쉬운 편이 아니라 저 티어를 받았다고 생각한다.

 

느낀 점

UCPC 화이팅