220513 팀 연습 (UKIEPC 2020)

qjatn0120, slah007 선배와 대면으로 하는 첫 팀연습이다.

셋은 UKIEPC 2020을 사용하였으며, 4시간 동안 진행하였다.

 

내가 A~D, qjatn0120 선배가 E~I, slah007 선배가 J~M을 보기로 했다.

 

~00:13

qjatn0120 선배가 E가 쉽다고 하셔서 컴퓨터를 넘겼는데, 틀리길래 B3 난이도인 D를 짜서 맞았다.

 

~00:26

이후 D와 똑같은 과정으로 slah007 선배가 J를 맞아오셨고, 나는 E AC 코드가 나오는 동안 C 풀이를 구상하고 있었다. 잘 가다가 59%에서 틀리길래 코너 케이스가 있을 것이라 생각했고, 모두 0인 경우를 예외처리 해주었더니 맞았다.

 

~00:45

선배들이 H, I, M을 맞아왔다. 이 문제들은 내용을 아직 몰라서 할 말이 없다. 나는 이때쯤 어려워 보였던 A, Constructive + Case Work인 B를 버리고 뒤쪽으로 가서 K를 봤다. 근데 뭔가 요새 코포에서도 많이 보고 자작 문제로도 생각하던 내용이길래 이건 풀고 간다는 마인드로 열심히 보았다.

 

~02:01

45분부터 이때까지의 컴퓨터는 대부분 B에 할당되어 있었다. K는 여러 방향의 풀이를 거쳐 최종 풀이에 도달했고, 그 동안 B의 하드코딩이 마무리되어 K 코딩에 들어갔다. 구상하면서 필요한 함수들을 대충 떠올려놨기에 구현은 빠르게 할 수 있었고, 한번에 AC를 받았다.

 

~02:39

남은 문제가 A, F, G, L이었는데 A랑 L은 너무 어려워 보였고, F는 바로 코딩을 들어갈 수 있다길래 G를 보았다. 하지만 G는 내가 싫어하는 원형 문제였고, qjatn0120 선배가 G의 그럴듯한 DP 솔루션을 제시하길래 확인만 해주고 A로 넘어갔다. F는 여러 번 틀리다 문제를 잘못 읽은 것을 깨닫고 AC를 받은 것 같았다.

 

~03:23

G는 배열을 뒤집는 과정에서 인덱싱 실수로 여러 번 틀리던 것 같았고, 나는 A를 끄적이다 G AC를 받은 것을 보고 놀았다.

 

문제별 요약

A (D3, Not solved) - \(O(N^2)\) DP처럼 생겼는데, 태그를 까보니 그리디만 있더라. 너무 어렵다

B (P3, solved by qjatn0120) - 18793의 10개 버전이다. 케이스 워크를 잘 하면 되는 것 같다.

C (G5, solved by leo020630) - 수열을 증가하는 단위로 끊어주면 된다. 마지막 또는 처음 원소가 0인지에 따라서 예외처리를 잘 해주어야 한다.

D (B3, solved by leo020630) - 상금의 합이 3의 배수인지 판별하자~

E (G3, solved by qjatn0120) - 안 읽었다.

F (P4, solved by slah007) - 다익스트라로 트리를 만들고 트리 DP 비슷하게 풀어주면 된다고 한다.

G (G1, solved by qjatn0120, upsolved) - 대회 중에는 DP로 풀었는데, MST 비슷하게 해도 된다고 한다. 발전소를 0번 도시와 해당 도시를 잇는 간선으로 해석해준 후 그냥 MST를 돌리면 된다.

H (B2, solved by qjatn0120 ,upsolved) - 주어지는 입력 중 아무 줄이나 출력하면 된다.

I (G1, solved by slah007, upsolved) - 수열을 1/4 단위로 끊어서 적절한 수를 넣어주면 된다. permutation이라 구현도 쉽고 아이디어도 어렵지 않은거 같아 G2 기여를 주었더니 티어가 P5에서 G1로 내려왔다.

J (S3, solved by slah007, upsolved) - 정수론과 케이스 워크를 적절히 해주면 된다.

K (D5, solved by leo020630) - 주어진 그래프를 펴주면 임의의 경로 하나를 얻을 수 있다. 이 경로의 XOR 값에 Cycle Basis들을 XOR해 구할 수 있는 최솟값을 구해주면 된다. 이는 가우스 소거법으로 해결할 수 있다. 풀었을 당시에는 P1이었는데 기여로 올렸다~ 신난다~

L (D5, Not solved) - 어려워 보인다.

M (B2, solved by slah007, upsolved) - 주어지는 세 개의 배열의 중앙값 배열을 만들어 출력하면 된다.

 

느낀 점

다이아를 대회 중에 풀어 기분이 좋았다

제출을 신중히 하자

우리 학교의 다른 팀이 제법 잘하는 것 같아 좋았다