BAPC 2020 팀 연습

BAPC 2020 팀 연습

  • 시간: 2021-03-31 13:15 ~ 18:15
  • 장소: 셀스스터디 부평

이번에는 BAPC 2020를 풀기로 했다. 코드포스에 없는 관계로 내 백준 그룹을 통해 연습을 했다.

여담으로 BAPC를 고른건 작년에 BAPC 연습 했을때 퍼포먼스가 좋았어서 이번에도 BAPC를 해봤다.

연습 타임 라인

13:15 ~ 14:12

Lemonade255가 H번 쉽다고 했다. 읽어보니 정말 쉬웠다. 풀어서 Solve.

13:32 H Solve

B번을 읽고 팀원들한테 얘기했는데 세명 다 똑같은 그리디 풀이를 생각해냈다. 근데 B번 코딩이 살짝 어려워서 C번을 읽었는데 C번도 쉬웠다. 단순 구현 문제 굳이 따지자면 그리디 문제였다.

그래서 C번을 짰는데 틀렸다. 생각해보니 조금 더 생각할 부분이 있었다. 예외케이스 처리를 좀 추가했는데도 틀려서 혼자서 생각하고 있었다.

B번은 dtc03012님이 짜는데 틀렸어가지고 Lemonade255가 반례를 찾아서 수정해서 풀었다.

14:03 B Solve +1

C번의 반례도 생각못하겠어서 Lemonade255가 디버깅을 했는데 $n = 1$일때가 반례였다. 역시 수정해서 AC

14:12 C Solve +3

~ 14:29

J번 읽는데 너무 쉬웠다. $w >= 2, h >= 2$ 조건도 있다는걸 읽고서 아 무조건 길이가 있으니 예외처리도 편하게 해줬네라고 잘못 생각하고 한번 틀리고, 수정 해서 맞췄다.

14:29 J Solve +1

~ 14:56

E번과 G번 문제는 어떤 문제인지 읽지도 못했는데 내가 J번 푸는 사이에 둘이서 쉽다고 하고 풀이 내서 코딩해서 풀었다.

14:39 E Solve 14:56 G Solve +1

~ 15:31

되게 여기까지 스무스하게 진행되었다. E,G를 Lemonade255가 짜고 있을때 F번 I번 문제를 dtc03012님이랑 풀이를 생각하고 있었고 좋은 풀이가 생각나서 말했다.

코딩은 dtc03012님이 한다고 해서 두문제를 코딩 했고 맞췄다.

15:16 I Solve +1 15:31 F Solve

연습 시작한지 절반이 안되었는데 8문제 풀고 3(A, D, K)문제만 남아서 되게 기분이 좋았다.

그러나 그 이후로 문제를 못 풀었다. ㅠㅠ

~ 연습 종료

D번 A번 K번을 다 읽어봤는데 다른문제랑은 다르게 풀이가 바로 나오지 않았다. 그나마 A번은 아예 모르겠고 D번과 K번이 좀 할만하다 생각했다. A번은 건드리지도 않았다.

D번을 푸는데 이분탐색이 필요한건 간단하게 생각할 수 있다. 높이 찾는건 쉬운데 이제 가로로 이분탐색이 안된다는 것이다. dtc03012님이 기울기 이분 탐색을 얘기했고, 그래서 내가 제시한건 양쪽 모서리 sky / sea 경계를 찾으면 기울기가 (낮은쪽 sky와 높은쪽 sea를 연결하는 기울기)와 (높은쪽 sky와 낮은쪽 sea를 연결하는 기울기) 사이에 있다는 것이 보장되니깐 거기서 이제 정수 좌표를 찾는다? 이걸 했는데 뭔가 잘 정리가 되지 않았다.

좀 더 고민을 하는데 갑자기 convex hull 이 생각이 나서 각도 순으로 넣고 정렬하면 찾을 수 있을것 같다 얘기했고 다른 사람들이 맞는거 같다 해서 내가 코딩을 하기로 하고, 나머지 둘은 K번을 열심히 토론 했다.

근데 구현을 너무 내가 못했고(풀이가 틀리니깐 잘짜기 쉽지 않다) ad-hoc식으로 정답이 잘 나오게 코드를 수정했지만 역부족이었다. K번도 별 발전이 없어서 이후에 세명 다 D번에 몰두 했지만 풀리지 않았다. 그리고 끝나기 직전에 이게 왜 안되는지를 깨달았다.

결과

BAPC 스코어보드를 보니 11등 정도 퍼포먼스다.

오피셜 솔루션 pdf도 존재해서 공부하기는 좋은것 같다.(대충 봤는데 아직 이해는 잘 안 된다.)

후기

맞은 문제는 크게 얘기할건 없고 이제 D번이 중요한 것 같다. 사실 D번은 기하(?) + 이분탐색 + 인터랙티브라서 짤때부터 좀 많이 틀릴걸 각오 했다. 과거에 Jerry and Tom라는 문제도 정말 고생해서 풀었어서 말이다.

양쪽 끝점을 이분탐색하고 그걸 잇는 선분에 후보가 위아래로 2000개라고 생각을 했고 linear search는 당연히 안되니깐 이분탐색처럼 해야한다는건 생각했는데 그 때 생각을 할 때는 가로로 그렇게 이분탐색이 안된다고 생각 했다.(한쪽 날리면 정답이 날라갈수 있는것 같았다.) 근데 풀이를 보니깐, 해도 되던데 아직은 정확하게 이해가 되지 않는다.

K번은 well-known 일거같은 냄새가 솔솔 났고 dtc03012님도 비슷한 문제 봤다고는 했는데 풀지는 못했다. 이런 xor은 항상 상위비트부터 잘 관리하거나 계산하면 되는데 풀이까지 연결되지는 못했다. 나는 offline query도 의심해봤지만 그런건 아니었다.

A번은 그냥 제일 어려운거같아서 손도 못댔다.

아마 다음 연습은 중간고사 전에 한번 더할수 있으면 하고 아니면 중간고사 끝나고 5월까지 되어야할것 같다.


구데기컵 오늘이였는지 몰랐는데 참여해야겠다.