UCPC 2021 예선 후기

14등

전공학점이 3.3 미만인 학생은 졸업고사를 봐야 졸업할 수 있다.

현재 내 전공학점은 3.28이다.

---

혹시 이전 대회글들을 본 사람들은 알겠지만, 원래 같이하던 내 팀원들이 다 군대와 사회로 사라져 버렸다.

대회나 상에 욕심이 없어지기도 해서 나가지 말까 고민을 했는데, 결국 적당히(?) 사람들을 모아 나가게 되었다.

 

팀원

ANZ1217, ruz, dongwoo338

 

의식의 흐름

일단 A를 보고 역시 수학은 체육과목임을 다시 한번 깨달았다.

바로 코딩해서 AC를 받았다.

 

0:03 A AC

 

그 후 문제를 쭉 훑어본 팀원들이 일단 BC가 쉬워보인다고 했다.

나는 C를 담당하기로 했다.

 

0:15 C AC

 

B를 풀던 팀원이 구현이 꼬였다고 해서, 내가 이어받아 마저 완성했다.

 

0:22 B AC

 

G가 조금 고민하면 답이 나올만한 Constructive 문제인것 같아 고민해보기로 했다.

그러는 동안 팀원들이 H를 풀어주었다.

 

0:34 H AC

 

G를 고민하는 시간이 조금 길어졌는데, 아무렇게나 입력을 넣어보다가 문득 소수의 배수를 넣으면 되지 않을까 하는 생각이 들었다.

2000보다 큰 소수 30개를 골라 이 소수들의 배수를 각 상자에 넣어봤더니 테스트 코드가 잘 돌아가길래 제출했다.

 

0:49 G AC

 

J번을 보다가, ruz님이 센트로이드로 풀릴것 같다고 했다.

듣고보니 맞는 말이라 바로 구현을 시작했다.

 

하는 동안 팀원들이 D와 I를 풀어주었다. 나는 이 문제들을 읽지도 못했다.

 

1:02 D AC

1:37 I AC

 

J번 코딩은 끝냈는데 예제가 안나오길래, 이유를 찾아 디버깅을 하다가 오타를 찾았다. 고쳐셔 제출했다.

 

1:41 J AC

 

이쯤에서 본선 진출은 확정이라 생각했다.

 

E와 F가 남았는데, F는 상위권에서도 푼 팀이 적길래 일단 E에 올인하기로 했다.

좌우의 기울기가 서로 다른 절대값(?) 그래프들의 함수값의 합의 최소값을 구해야 됐었는데, 비슷한 다른 문제에서 이런 그래프가 볼록하다는 사실을 알고 있었다.

이 그래프도 아마 그럴것 같이 보여서, 볼록한 그래프의 최소값을 찾는 문제로 생각하고 풀었다.

전체적으로 슬라이딩 윈도우의 형태에서 윈도우가 이동할 때마다 각 그래프들이 추가/삭제 되므로, 유동적으로 기울기와 함수값들을 관리하기 위해서 세그트리를 이용했다.

 

마지막에 의문의 맞왜틀을 몇번 당했는데, 역시나 오타가 있었다. 수정해서 제출했다.

 

2:39 E AC

 

이쯤에서 F를 굳이 풀어야 할까 생각했다.

 

그래도 문제를 읽고 풀이를 생각해보니 3개의 서로 다른 집합에서 수를 각각 꺼내, 합이 m이 되게 하는 경우의 수를 구해야 했다.

이걸 어떻게 할지 고민하다가 대회가 끝났다.

 

나중에 천천히 생각해보니 FFT인가 싶었는데 그게 정해가 맞았다고 한다.

 

재미가있었다