본문 바로가기

PS81

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$인 쌍이 있는지를 검사.. 2026. 2. 7.
2026년 1월 다섯째 주 PS 일지 1/26 월요일선발 전까지 매일 5시간짜리 섭테문제 4제 셋을 돌려고 합니다.오늘은 16777 32040 30941 15865로 구성된 셋을 돌았습니다.각각 100 100 110(110점 만점이래요) 46점을 받았고 마지막 문제도 바로 업솔빙했습니다. 문제에 대한 정보 하나도 없이 셋을 구성하다 보니 굉장히 쉬운 셋이 나왔는데 잘 한것 같습니다. 16777 Election Campaign: 트리 DP를 ETT 느갱섹으로 최적화32040 Naval battle: 레전드 pq + 셋질 + 구현30941 Dizalo: 루트질15865 Genetics: 랜덤한 값을 각 문자열에 주고 해싱을 하면 각 문자열당 특수 문자열인지 $O(M)$에 확인이 됩니다. 22198 Toll: 행렬 세그31068 균형 잡힌 등급.. 2026. 2. 2.
BOJ 15842 - Koala Game 풀이와 증명을 이해해볼겸 이 글에 문제의 풀이를 정리하겠습니다. 문제 요약입니다 ㅎㅎ 서브테스크 1 (4점, 최솟값 찾기, $C_{max}\le 2$)$0$번째 값에 $1$만큼 배팅합니다. 코알라는 어떻게 해도 $99$개의 값만 먹을 수 있기에 최솟값을 제외하고 모두 먹을 것 입니다.따라서 $R_i=0$인 $i$가 답이 됩니다.int minValue(int N, int W) { int B[N], R[N]; fill(B, B + N, 0), B[0] = 1, playRound(B, R); for (int i = 0; i 서브테스크 2 (15점, 최댓값 찾기, $C_{max}\le 4$)다음 과정을 반복해서 풀 수 있습니다.1. 최댓값 후보 $S$가 있다고 하자. 이 집합에 속한 인덱스에.. 2026. 2. 1.
2026년 1월 넷째 주 PS 일지 1/19 월요일18456 Jealous Split: alien trick을 쓰지 않는 중국인 풀이로 풀었습니다. 중국인 블로그에 그냥 방법만 써있길래 증명을 열심히 해서 성공했으나 귀찮으니 소개는 안하겠습니다. 1/20 화요일27607 학생들: 도는 횟수를 구하는 방법을 잘 찾으면 됩니다.18081 Balanced Cut: 가장 작은 수 부터 가능한지 판별해줍니다.24486 Counting Haybales: 홀짝을 나눈 뒤 전이 가능을 잘 정해주고 DP를 해줍니다.35112 으악그래프: $M>N$이면 스패닝 트리를 제거했을 때 간선이 $2$개 이상 남으므로 No 입니다. 1/21 수요일23477 Evacuation: 적당한 관찰 후 스위핑 + 셋질20603 Count on a Tree || Strikin.. 2026. 1. 26.
2026년 1월 셋째 주 PS 일지 1/12 월요일ABC | 우주정거장 2 | No Cycle | 장난감 | 패턴 매칭 로 이루어진 셋을 돌았습니다. 우주정거장 2를 제외하고 다 풀어서 400점을 획득했습니다. SCPC 2022 2차 예선 ABC: 재귀 DP를 해줍니다. 무한 처리가 좀 까다롭습니다.SCPC 2018 본선 우주정거장 2: 최대한 삼각형을 제거해준 뒤 단절점에서 가능한 경우를 모두 곱해줍니다.SCPC 2021 1차 예선 No Cycle: 그리디하게 방향을 배정해줘도 문제가 되지 않습니다.SCPC 2023 1차 예선 장난감: 일단 최대한 퍼뜨린 뒤 Z 알고리즘으로 주기를 찾습니다.SCPC 2021 2차 예선 패턴 매칭: 비교 가능하게 문자열을 바꾼 뒤 해싱을 잘 써줍니다. 25008 문자열 찾기: 패턴 매칭31736 Islan.. 2026. 1. 19.
ARC 183 E - Ascendant Descendant https://atcoder.jp/contests/arc183/tasks/arc183_e E - Ascendant DescendantAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 문제 요약은 안하겠습니당 ㅎㅎ. 이번 겨울학교 모의고사에 나온 문제입니다. 제가 이 문제를 비교적 쉽게 푼 것 같아서 풀이를 설명해 보고자 합니다. 일단 $i$와 $i+1$이 swap이 가능한 필요충분조건은 $max(depth[A[i]], depth[A[i+1]]) \le depth[lca(B[i], B[i+1])]$인 것입니다. 이 조건만 만족.. 2026. 1. 12.

티스토리툴바