hibye1217, tlsdydaud1과 팀 OReO로 UCPC에 나갔다.

학교 도서관 스터디룸에 모여서 진행했다. TV에 스코어보드를 띄우는 건 실패했지만, C번 풀이를 공유할 때 화이트보드가 도움이 됐다.

예비소집 때 UCPC에서 가장 쉬운 문제 번호는 A라는 말이 기억나서 hibye1217이 A~C, 내가 D~F, tlsdydaud1이 G~J를 보기로 했다.

경과

hibye1217이 A를 바로 풀었다. 그 후 다들 무엇을 풀지 고민하는 시간이 조금 있었다.

F가 쉽길래 내가 F를 짰는데 WA를 받았다. F를 디버깅하는 동안 B가 단순 그리디가 아니냐는 말이 나왔고, 맞는 것 같다는 의견에 힘이 실리면서 hibye1217이 B를 풀었다.

F WA 코드에서 \(M\) 대신 \(N\)을 쓴 사소한 실수를 발견해 고치니 AC를 받았다.

[0:01:34] A AC

[0:22:07] F WA

[0:27:42] B AC

[0:28:08] F AC

D 풀이를 찾았다. pbds와 유리수 구조체를 사용하는 풀이였는데, pbds를 써본 적이 없어서 구글링하면서 멍을 좀 때렸다.

그때 J 문제 설명을 간단히 듣고 풀이를 냈다. 이미 tlsdydaud1이 풀이를 냈던 상태여서 별로 도움은 안 됐다. tlsdydaud1이 J를 맞았다.

쉽게 풀릴 문제가 더 없다고 판단한 tlsdydaud1이 E를 잡았고, AC를 받았다. 그 즈음에 hibye1217이 카탈란수 어쩌고 하더니 H AC를 받아왔다.

한편 나는 D 구현 과정에서 pbds를 multiset으로 쓰는 법을 모르겠어서 얼을 타다가 이 풀이를 버렸다. (pair<fraction, index>로 저장하면 그냥 set으로 해도 된다는 걸 대회 끝나고 알았다)

삽질을 좀 더 하다가 2번 쿼리에서 \(c\)가 정수이니 \(k < -\frac{b}{a} < k+1\)인 정수 \(k\)만 중요하다는 것을 깨닫고 동적 세그를 사용하는 풀이를 냈다. \(a<0\)인 케이스에서 최고차항의 부호를 뒤집어주는 걸 깜빡해서 WA를 2번 받고 AC를 받았다.

내가 D를 푸는 동안에 hibye1217과 tlsdydaud1이 G를 잡았고, tlsdydaud1이 WA를 2번 받은 후 AC를 받았다.

[0:34:19] J AC

[1:02:04] E AC

[1:04:00] H AC

[1:24:23] D WA

[1:30:20] D WA

[1:33:22] G WA

[1:35:40] G WA

[1:36:46] G AC

[1:42:24] D AC

C랑 I가 남은 상태로 우리팀 스코어보드도 프리즈됐다. 프리즈되지 않고 C를 푼 팀도 있고, C 제출이 I보다 많길래 C부터 보기로 했다.

C 풀이가 나와서 팀원들에게 공유했다. “구현 해줘”를 외치고 I를 잡으려다가 C도 못 풀 거 같아서 나도 구현에 합류했다.

\(N\)이 50만이어서 multiset을 쓰면 TLE가 날까봐 PQ를 사용하는 투포인터 풀이로 발전시켰다.

열심히 구현하다가 시간이 부족해 포기를 선언했는데 hibye1217이 갑자기 제출하더니 AC를 받아왔다. multiset을 써도 시간이 넉넉하다고 한다..

끝나기 전에 hibye1217이 ‘편지 써서 제출하면 특별상 주나요’를 출력하는 코드를 제출했다.

[2:57:38] C AC

[2:57:50] I WA

후기

내가 D랑 F에서 3틀만 안했으면 한자릿수 등수 받을 수 있었는데 아쉽다.

D에서 시간을 아꼈으면 I까지 노려볼 수 있지 않았을까 싶다. 팀노트의 필요성을 느꼈다.

이상한 문제들을 팀원들이 다 풀어줘서 든든했다.

대회 끝나고 C번 풀었는데 PQ+투포인터랑 multiset이랑 시간 차이가 안 나더라..