220624 팀 연습 (SUAPC 2021w)

셋은 SUAPC 2021w을 사용하였으며, 동아리의 다른 UCPC 출전 팀들과 함께 3시간동안 진행하였다.

 

~0:05

qjatn0120 선배가 앞쪽, 내가 뒤쪽, slah007 선배가 가운데를 보기로 하고 시작하였다. J~M을 본 나는 J를 일단 거르고 K가 쉽다는 것을 깨달아 짜서 맞았다. 

 

~0:11

slah007 선배가 본인의 문제를 헷갈리는 해프닝이 있었지만, 쉬운 문제였던 B와 I를 qjatn0120 선배와 slah007선배가 각자 짜서 맞았다.

 

~0:19

이후 내가 L 풀이를 구상해 짜서 맞았다. qjatn0120 선배는 구현량이 많은 A를 잡았으며, slah007 선배는 H를 잡았다.

 

~0:24

H AC가 나왔다. slah007 선배는 F를 풀러 갔으며, 나는 J랑 M이 쉽지 않다는 것을 깨닫고 남은 문제들을 한바퀴 둘러보았다.

 

~0:43

남은 문제들을 훑어본 내가 Simple DP인 C를 맞아왔다. 

 

~1:02

F의 AC가 나왔다. 나는 둘러본 문제 중 깡 수학이었던 E를 slah007 선배에게 던지고 J를 풀러 갔다.

 

~1:23

기나긴 구현 끝에 A AC가 나왔다. 나는 J의 풀이를 열심히 생각 중이었으며, A를 푼 qjatn0120 선배는 D를 잡는 듯 하더니 포기하고 G를 잡으셨다.

 

~2:25

J 문제를 헷갈려서 코드를 여러번 갈아엎은 끝에 AC를 띄웠다. 그동안 qjatn0120 선배는 G 식을 열심히 정리해오셨고, 내가 2-SAT을 구현하기로 했다.

 

~2:56

G 코드를 다 짰는데 예제가 나오지 않아 고민하던 찰나, 내가 그냥 2-SAT을 헷갈려서 식을 이상하게 적었다는 점을 깨닫고 고쳤더니 바로 AC가 나왔다. 그렇게 10솔으로 연습을 종료하였다. 5시간짜리 대회지만, 아마 2시간을 더 했어도 1솔 정도를 더 했을 것 같다.

 

문제별 요약

A (P4, solved by qjatn0120) : 구현이 더럽다는 소리만 듣고 문제를 보지 않았다.

B (S4, solved by qjatn0120) : 같은 원소의 등장 횟수 중 최댓값을 출력하면 된다.

C (G1, solved by leo020630) : 기댓값 식을 쓸 줄 안다면 누적합+Simple DP로 바뀐다.

D (D5, Not solved) : 오일러 지표+기하 구현 문제인데 시간 상 아무도 잡지 않았다.

E (D4, Not solved) : 정수론 문제라 우리 중 이런걸 가장 잘하는 slah007 선배가 1시간 넘게 잡았는데도 풀지 못했다. 많이 어려운 문제인 것 같다.

F (G1, solved by slah007) : 반전->비트 한개 빼고 바꾸기가 된다는 점을 추측할 수 있고, 그레이 코드를 이용하면 이를 잘 구현해 줄 수 있다. 여러 조건이 붙어서 구현이 좀 더럽다.

G (P1, solved by qjatn0120, leo020630) : 2-SAT 문제같이 생겼고, 실제로도 그게 풀이이다. 비트 별로 노드를 만들어주면 되는데, 정리해야 할 식이 좀 까다롭다. 

H (G4, solved by slah007) : 어디서 많이 본 약간 뻔한 문제다. 원래는 예외처리가 좀 필요한데, 그냥 __gcd로 나눠주면 잘 되더라.

I (B3, solved by slah007) : aaaaaa

J (P3, solved by leo020630) : 문제가 원하는 바를 이해하면, Set 등으로 구간의 길이를 관리하며 최솟값을 찾으면 됨을 알 수 있다. 시간을 줄이기 위해서는 추가로 이분탐색 혹은 투포인터를 사용해야 한다. 

K (G5, solved by leo020630) : 소인수분해를 한 후 앞에서부터 2개씩 

L (G4, solved by leo020630) : 건물 또는 잔해의 위치를 저장해준 후 누적합 또는 이분탐색으로 폭탄이 있을 수 있는 모든 곳에 폭탄을 설치하면 된다.

M (D3, Not solved) : 너무 어렵다

 

느낀 점

스케줄링이 안 꼬이려면 가리는 분야가 없어야 할 것 같다. 수학 공부를 하자