Functioncup 2023 후기

결과

79brue, kizen과 함께 굿바이 한별이라는 팀 이름으로 참가했다. 총점 26점으로 전체 9등, 진영 5등을 했다.

아마 올해 UCPC도 같은 구성으로 나갈 가능성이 크다.

 

팀 연습

1068점, 스코어보드상 2등

아무래도 기출문제를 풀어보고 가는게 좋을 것 같아서, 함수컵 2019를 돌았다. 나와 kizen은 같은 학교라서 본관에서 했다. 나는 사실상 한게 없다.

 

처음에는 마지막 4문제를 잡았는데, 42와 43을 풀었다.(43은 구현은 안 했다) 이후 문제들이 빨리 풀려서 내가 할 것은 23밖에 없었고, 8x점의 풀이를 냈으나 구현을 하지 못 해서 49점만 받았다. 끝나고 풀이를 봤는데, 처음 접근 방향이 완전히 틀렸었다.

 

타임라인

함수컵 2019에서 마지막 4문제는 대체적으로 어려웠고, 내가 세 명 중에서 제일 못 하므로 내가 가운데 문제를 잡기로 했다. KL, MN, OP, QR을 잡기로 했다. 문제 이름이 두 글자라서 소통하는데 약간의 불편함을 겪었다.

 

0:00 ~ 0:16

일단 네 문제 다 읽었다. MN이 다른 문제에 비해 쉬워보인다는 것을 알게 되었지만, 앳코더식 패널티 산정 방식에 의해 문제를 다 읽고 구현해도 패널티에 문제는 없어서 다른 문제를 다 읽고 왔다. 이후 MN의 스택 풀이를 짰다. 이상한 실수로 한 번 틀리고 맞았다. 이 시점에서 79brue가 CD를 풀었다.

0:17 ~ 1:09

OP와 QR을 생각해보다가, 별다른 진척이 없어 KL로 왔다. 각 $S_i$에 대해 $S_i=Lx+Ry$로 나타낼 수 있는 순서쌍 $(x, y)$는 확장 유클리드 알고리즘으로 구할 수 있고, 이 값들(등차수열을 이룬다)을 관리해주면 풀 수 있다는 것을 관찰했다. 이것저것 처리해야 할 것이 많아서 좀 오래 걸렸는데, 결국 맞았다. 중간에 1-based를 0-based로 착각해서 한 번 틀렸다.

1:10 ~ 1:38

내가 맡은 문제 중 남은 문제인 OP와 QR을 번갈아 고민했다. OP은 1점도 생각이 안 났고, QR는 그럴듯한 다항식 시간 복잡도의 dp가 생각났는데, 이 시점에서는 구현하지 않았다. kizen이 YZ가 계속 틀린다고 해서 도와주러 갔다.

1:39 ~ 2:15

kizen의 코드 중 도저히 틀린 지점을 찾을 수 없어서 내가 다시 짰고, 틀렸다. 이 시점에서 패널티는 포기하기로 했다. 3시쯤 kizen 코드의 반례를 찾았다. 그 외에도 dsu를 많이 초기화하는 등 시간 복잡도가 커서 줄였고, 고쳤는데 2점이 떴다. 상수가 커서 풀테가 안 돌았으리라 생각하고 다른 문제로 넘어갔다.

5 5 0
00000
00000
00000
00000
00000

내가 찾은 반례이다.

2:16 ~ 2:45

아까 QR 2점 풀이를 구현했다. $a_i > a_{i+1}$인 $i$의 집합과 결과로 나올 수 있는 순열이 일대일대응된다는 사실을 이용하면 풀린다.

2:46 ~ 3:43

ST를 생각했는데, 별 소득이 없었다. 4시쯤부터 WX 섭테 1, 2를 구현하기 시작했다. 섭테 1은 십자가 정가운데, 왼쪽 위 칸을 지나는 가로선 세로선을 그리면 되고, 섭테 2는 삼각형의 직각 오른쪽 아래 점을 지나는 가로선과 세로선을 그리면 된다. 구현을 하는 중, 4시 9분쯤 YZ의 2점이 상수가 문제가 아니었다는 사실을 알게 되었다.

 

서브태스크의 위계가 잘못 설정되어 있었다.

$R=1$섭테만 틀린 상황이었고, 난 WX를 구현하던 중이라 kizen이 예외처리를 해 주었다.

 

3:44 ~ 5:00

이것저것 해 보았는데, 딱히 소득은 없었다. ST에서 그럴듯한 그리디 풀이를 내고, WA를 받았다. WX 섭테 3에서 문지르기 없이 풀 수 있는 문제가 문지르기 없이 풀 수 있는 문제와 동치라는 사실을 알게 되었고, 이를 79brue에게 전해주었다. 그러나 추가적인 점수로는 이어지지 못 했다.

 

 

같이 보면 좋은 글

https://79brue.tistory.com/43

FunctionCup 2023