2025년 8월 둘째 주 PS 일지

8/11 월요일

IOI 2023 Day 1을 4시간 정도 돌았습니다.

43 60 8을 받았습니다. 얼마 지나지 않아서 3번 54점 됐는데 ㅠㅠ

 

29746 Longest Trip: 85점까진 자력했어요! 경로 $2$개 잡고 $2$개씩 $3$개의 쿼리로 잘 추가해 주고 이분탐색 적당히 $2$번 해서 경로 합쳐주면 됩니다.

 

8/12 화요일

IOI 2023 Day 2를 4시간 정도 돌았습니다.

31 65 35을 받았습니다. 낫밷. 시간 좀만 더 있었으면 2번 풀테 노리거나 3번 54점 노렸을 듯.

 

34115 먼 카드

34118 부산 관광: 자명 DP

34119 건초 더미: ^자료 구조^

34120 무궁화 꽃이 피었습니다: 정점 $O(N^2)$개 잡고 다익스트라

34121 택배 운송: 트리를 직선으로 피고 적당한 전처리를 한 뒤 ^자료 구조 22^

 

29747 Soccer Stadium: 직사각형 합집합의 최소 넓이를 구하면 되는데 놀랍게도 state와 전이가 모두 $O(N^2)$개라 잘하면 됩니다. 

 

8/13 수요일

여학 마지막 날이라서 2차 모의고사를 봤어요!

저번과 똑같이 2등이 목표였는데 또다시 1등을 했습니당. 🥰🥰

야호

 

대충 스코어보드는 이렇고 코치 피셜 다(3~2) 다(3~2) 루 다(5~4) 셋에서 100 100 5 9를 받았습니다!

1번과 2번 모두 2시간씩 걸렸습니다! 1번은 좀 섹시한 문제였고 2번은 자명한 관찰에 자구질좀 하면 되는 문제였습니다!

모의고사는 딱히 중요한 대회는 아니긴 하지만 kuhyaku를 2연속으로 이기고 유담이나 재원이나 에그같은 잘하는 친구들도 2연속으로 이겨서 자신감이 생기고 기분이 좀 좋았어요!

아 물론 4번 못푼거는 아쉽지만, 난이도 대비 푼 사람이 많이 적어서 다행이였어요.

26794 Konkurs tańca towarzyskiego: 모고 1번이에요! 노드 복제 관계를 트리로 표현하고 열심히 관찰하면 ETT + 세그로 풀 수 있어집니다.

18424 Matching: 모고 2번이에요! 

같은 $x$좌표나 $y$좌표를 가지면 간선을 이어주면 컴포넌트가 여러개 나옵니다. 각 컴포넌트는 사이클이나 경로인데 사이클인 경우 모든 매칭을 $x$축 방향으로 하거나 $y$ 축 방향으로 해도 되지만 경로면 방향이 확정됩니다. 이때 컴포넌트끼리 교차하는 경우도 있는데 컴포넌트끼리 교차하고 방향이 다르다면 문제가 생겨요. 그래서 교차하는 컴포넌트끼리 잘 유니온 파인드를 해줘야 하는데 직선이 교차하면 유파하는 거는 안전지대 하위 호환이기 때문에 이를 그대로 구현하면 됩니다.

 

8/14 목요일

18605 Coins: $a_i\le b_i$인 경우랑 $a_i\ge b_i$인 경우에 대해서 각각 나눠 그리디를 해준 뒤 dnc opt 비슷하게 merge 해주면 됨

29745 Closing Time: 미친 그리디

29749 Overtaking: 세그 셋질 전처리 영차영차

 

8/16 토요일

32447 Make Them Meet: 트리에서 해법은 두 노드 사이에 가두면 되고요 그래프에선 괜찮은 스패닝 트리를 뽑은 뒤 잘해주면 됩니다.

 

8/17 일요일

29748 Beech Tree: 필요충분조건을 깔끔하게 잘 찾으면 간단한 스투라 셋질로 풀림

 

NYPC Round 2A를 했어요!

 

1시간 만에 1, 2, 4번을 풀고 3번 풀테를 노리다가 그냥 2시간 22분에 349 받고 끝났습니다. 시간이 좀 남긴 했었는데 학교도 가야 하고 저 정도면 충분히 본선 진출권이라고 생각해 그냥 저 정도 받고 마무리했습니다.

 

끝나고 이야기를 나눠보니깐 제가 제일 잘 본 것 같아요. 우하하