2025년 8월 첫째 주 PS 일지

8/4 ~ 8/13 여름학교 갑니다!

 

8/4 월요일

34088 It's a Mod, Mod, Mod, Mod World 2: 무작위화로 $K$의 후보를 $100log 10^9$개 정도 만들어서 시뮬레이션해 봅니다.
34086 트리 이사: 답은 (리프노드 + 1) / 2이며 구성은 dfs ordering으로 정렬한 뒤 반으로 갈라 잘하면 됩니다.

34080 일천광년: 수학을 열심히 하면 답이 간단하게 나옵니다.

 

여름학교에서 IOI 2022 Day 1을 했는데요, 전 2번이랑 3번이 이미 풀었던 문제였습니다.

그리고 뭔가 일이 있었는지 5시간보다 짧은 3시간만 하고 마쳤습니다.

 

25438 메기 농장: 최적해 관찰과 상태 수 $O(M)$ 관찰을 한 뒤 DP를 해주면 됩니다. 갓문제

 

8/5 화요일

오전에는 15575, 17096, 18195로 이루어진 3시간 셋을 돌았습니다. 

 

15575 신호 2: $x$좌표당 가장 높은 점과 낮은 점을 남긴 후 DP

17096 Tourist: 다익스트라 트리?에서 간선 합 최소화

18195 정점 찾기: 셋 돌 때 풀지 못해서 업솔빙했습니다. 두 수의 XOR 값을 $7$회에 알 수 있으니 같은 비트에 대해서는 $1$회씩 최악의 경우에도 $13$ 회 안에도 두 수를 찾을 수 있습니다.

 

오후에는 IOI 2022 Day 2를 2~3시간 동안(잘 기억안남) 돌았습니다.

아마도 18 98.64 100을 받았습니다. 사실 3번은 이미 풀어본 문제였습니다.

 

25441 디지털 회로: 식정리가 매우 이쁘게 독립적인 형태로 가능해 자료구조를 해주면 됩니다.

25442 드문 곤충: 이분탐색을 이용해서 일단 답을 구할 수 있고 매번 기계에 넣을 후보를 반씩 줄여줘 $3N+\alpha$개의 쿼리로 가능합니다.

 

8/6 수요일

오전에는 19333, 25728, 31159로 이루어진 2시간 반? 셋을 돌았습니다.

 

19333 Subsequence Sum Queries: CDQ

25728 Connecting Cables: $x$값과 $y$값 분리 후 더블카운팅

31159 Max Pair Matching: EA 그리디

 

오후에는 IOI 2021 Day 1을 2시간 동안 돌았습니다.

40 9 15를 받았습니다. 2번은 이미 푼 문제여서 풀테 구현하다가 2시간 안에 못 했습니다.

 

22023 Distributing Candies: 누적합 그래프에서 차이가 $C_i$인 마지막 부분을 자료구조로 찾은 뒤 남은 값 계산

22025 Fountain Parks: 체스판 칠한 후 각 색에 대한 규칙을 만들고 잘하면 됩니다. 어찌저찌 연결된다는 것이 증명됨.

 

34096 자동 광고 배치 시스템: DP 테이블로 세그 이용

34098 Only Shallow: 필요충분조건을 찾은 후 2-SAT

 

8/7 목요일

10175 JOI 공원: 다익스트라를 돌린 후 간선 정렬하면 걍 풀림

 

오늘은 어떤 대회 이슈로 계학을 빠져나와 아무 셋도 돌지 않았습니다!

 

8/8 금요일

IOI 2024 Day 1을 5시간 동안 돌았습니다!!

100 100 59를 받았습니다. 사실 1, 2번 모두 이미 푼 문제입니다.

 

32264 Tree: 가장 작은 정점을 잡고 계산하고 빼고 트리 분리하고 반복

 

8/9 토요일

모의고사를 봤어요!

 

20699 20344 32447 25118로 이루어진 5시간 셋이였고 100 73 34 100을 받아 1등을 했습니다!! (2번은 강화 버전)

kuhyaku를 발랐어요!!

 

20699 Almost Balanced Tree: 2를 최대한 루트로 하는 전략으로 재귀

20344 Exam: 구간 그래프로 환원 후 DP

25118 Compairing Fractions: 대분수의 정수부 비교하고 뒤집고 반복

 

8/10 일요일

IOI 2020 Day 1을 5시간 동안 돌았습니다.

32 100 100를 받았습니다. 다 처음 보는 문제인데 괜찮게 결과가 나온 것 같아요!

 

19933 Compairing Plants: DAG 구성할 수 있으니 가장 넓은 범위를 세그 + 스파스로 잘 찾기

19934 Connecting Supertrees: 적당히 유파하면서 구성

19935 Carnival Tickets: MCMF 모델링 한 후 한 싱크에 몰빵 후 PQ 그리디

 

선발 이후 실력을 측정받을 일이 없었는데 여기 와서 셋 많이 돌고 모의고사도 쳐보니깐 실력이 많이 늘었음이 느껴져서 기부니가 좋습니다.

 

문제가 많아서 문제의 설명을 개대충썼는데 죄송해용ㅠ