2026년 2월 첫째 주 PS 일지

2/2 월요일

오늘은 18848 28058 14875 19927로 구성된 셋을 돌았습니다.

100 11 100 100을 받았습니다.

 

첫 문제 그냥 센트 쓰면 딸깍인데 생각 못하고 큰작 + 유파로 엄청 고생해서 풀었어요. 대신 스트레스 짜고 시간 안에 맞아가지고 다행입니다. 3, 4번을 보자마자 푼게 잘한것 같아요.

 

18848 Capital City: 트리 압축을 한 뒤 가상 노드 만들어주고 간선 이어주고 유니온 파인드 + 큰작을 열심히 해주면 됩니다.

14875 City Attractions: 전방향 트리DP로 갈 노드를 정해주고 함수형 그래프에서 빙빙 돌면 됩니다.

19927 Vision Program: 좌표축을 45도 돌린뒤 정사각형 안에 속하는지 + 딱 x좌표 차나 y좌표 차가 $K$인 쌍이 있는지를 검사해주면 됩니다.

 

2/3 화요일

오늘은 24942 10922 5811 10921로 구성된 셋을 돌았습니다.

100 100 55 34를 받았습니다.

 

오버킬이긴 하지만 구현 뻘짓 없이 1번을 풀고 3, 4번을 풀테 - 1 (- 풀테랑 제한 2배밖에 차이안나는 이상한 섭테) 까지 짰으니 매우 제 기준으로 잘했다고 할 수 있습니다. ㅎㅎ

+ 3번을 업솔빙했더니 이걸 왜 못풀었나 싶긴 하네요

 

24942 Jail: 필요충분 조건을 따지면 $S_i - T_i$ 경로 위에 $S_j$가 있으면 $i$에서 $j$로 간선을 이어주고 경로 위에 $T_j$가 있다면 $j$에서 $i$로 간선을 이어준 그래프가 DAG인 것입니다. 간선 잇기는 바이러스처럼 센트로이드를 이용하면 쉽게 할 수 있습니다.

10922 말: $A_i=1$인 $i$들은 셋으로 적당히 구간으로 관리하고 하나의 노드로 여깁니다. 그러면 답의 후보는 $N-64...N$에 있어서 나이브하게 탐색해 줄 수 있습니다.

5811 낙하산 고리들: 최대 degree가 2 이하인 경우, 3인경우, 4 이상인 경우 잘 처리하면 됩니다. 특히 최대 degree가 3 이상이면 답의 후보가 4개 이하라는 점에서 유니온 파인드를 4개 관리해주면 됩니다.

10921 팀들: 스택 + pst

 

2/4 수요일

오늘은 17678 15557 14423 27460으로 구성된 셋을 돌았습니다.

100 75 100 67.13을 받았습니다.

 

4번을 못 푼게 아쉽긴 하지만 모든 문제에서 고득점을 받아 이상적인 결과라고 생각합니다.

 

17678 합병: 트리 압축해서 묶어줄 간선 구하기 + 이후 리프 노드 / 2

15557 Snake Escaping: $min(?, 0, 1) <= \frac{L}{3}$이므로 각각에 대해 SOS DP + 포배 $2^{L/3}$을 돌려주면 됩니다.

14423 Rope: 필요충분조건을 나이브로 잘 찾으면 인접한 두 수씩 쌍이 되게 한 후 이들이 같은 색이여야 함을 알 수 있습니다. 따라서 이거를 선형에 잘 관리해주면 됩니다.

27460 Where is the Root?: 22회 쿼리는 센트로이드 분할 + 많은 조건 분기로 도달 가능합니다. 9회는 리프 노드를 앞에 두고 나머지를 뒤에 둔 배열에서 Yes가 되는 지점을 이분탐색으로 찾으면 됩니다.

 

28058 Tsunami: DP + 리차오 레이지

 

2/5 목요일

오늘은 17697 25434 19556 23063 셋 돌았습니다.

20 40 9 64를 받았습니다.. ㅋㅋ

 

4번은 풀테를 짰지만 상수컷팅에 실패했고 2, 3번은 능지이슈로 못풀었습니다. 1번은 그냥 어려운 문제고요. 3번 점수가 아쉽긴 합니다.

 

25434 Magic Cards: $mod 7$로 동일한 두 친구를 잡고 $10010$ 위의 원에 올려가지고 더 작은 쪽을 남은 $6$개로 인코딩하면 됩니다.

19556 Colors: 딱 $log 10^18$만큼 쓸 수 있으므로 지그재그로 답을 구합니다. 답이 $N-1$일 때 나가지 않게 하는 시작점을 구하면 됩니다. 이게 왜 겹치지 않고 다른 경우에서도 밖으로 나가지 않는지는 증명이 필요할 것 같은데 찾지 못했습니다. 혹시 알게 되면 알려주세용

23063 Diversity: 개수 순으로 나열해 왼쪽 오른쪽 번갈아가면서 붙인 꼴이 최소가 됨을 알 수 있습니다. 쿼리는 mos + 서로 다른 수의 개수가 sqrt개임을 이용하여 루트로그를 짜고 컷팅을 열심히 하면 돕니다.

 

2/6 금요일

오늘은 21795 5814 12754 23065로 구성된 셋을 돌고 처음으로 올솔을 했습니다! (3번은 백준에선 68점이지만 qoj에선 100이므로 ac라 치겠습니다 ㅎㅎ)

 

21795 Worst Reporter: 사이클을 대충 묶어주면 트리가 나옵니다. 트리에서 dp를 하는데 상태를 $(x, y)$: $dp[i][j] (j \ge x)$에 $y$를 더한다 의 set으로 관리해주면 풀립니다.

5814 마상시합 토너먼트: 트리로 만들어준 뒤에 위치에 따른 분할정복을 해주면 됩니다.

12754 스왑: 자명한 DP를 하는데 그리디를 잘 해주면 상태가 $O(NlogN)$개밖에 존재하지 않아 잘 해주면 됩니다. 백준에선 tl이 쓰레기에요;

23065 Newpapers: 필요충분조건이 대충 $deg=1$인 정점들을 모두 지워준 그래프가 트리이고 지름을 잡았을 때 지름에 포함되지 않은 노드의 차수가 $1$인 것입니다. 따라서 이 정점들을 지름의 홀짝성에 따라 잘 해주면 됩니다. 증명은 못하고 나이브 돌렸더니 저렇게 나와서 풀어줬습니다.

17697 Railway trip: 트리로 모델링 해준 뒤에 스파스 테이블을 잘 써주면 됩니다.

 

2/7 토요일

오늘은 15864 16782 31818 27461로 구성된 셋을 돌았고 74 100 61 100을 받았습니다. 끝나고 6분 뒤에 1번을 풀었기에 중간에 디코에서 안놀고 빡집중했으면 어떘을까 아쉽긴 하네용.

 

15864 Alternating Current: 적당히 포함되는 구간을 제거해준 뒤에 $0 1 0 1$을 배정해주면 됩니다. 홀수면 $1 1$인 경우가 존재하는데 이래도 괜찮은 인덱스를 적당히 찾아주면 됩니다.

16782 Amusement Park: 스패닝 트리를 잡아줍니다. dfs를 하면서 모든 노드가 크기가 $60$인 어떤 연결된 서브트리에 포함되게 잘 해주면 됩니다.

31818 Discount Event: 트리 모스 + Dynamic Diameter을 시도하다가 풀테는 실패했습니다.

27461 Bounded Spanning Tree: 가중치 간의 관계를 구할 수 있습니다. 이후 Dumae를 해줍니다.

 

31442 좋은 수열: 필충을 찾고 세그로 관리

33053 All Pairs Similarity: 상위 $k$개의 비트만 봤을때 $popcount(x|y)$랑 sum $popcount(x&y)$를 가지고 하는 비트DP를 하면 됩니다.

 

2/8 일요일

2207 가위바위보: 2-sat 연습

1298 노트북의 주인을 찾아서: 이분매칭 연습

28336 맑은 하늘 프로젝트: DP

 

2차 선발고사를 봤습니다.