2025년 7월 셋째 주 PS 일지

7/14 월요일

17671 두 안테나: 섹시한 세그먼트 트리를 짜고 스위핑을 잘하면 됩니다. 30분도 안 걸려서 자력 했어요!!
11474 Insider's Information: $b_i$로 안쓰이는 어떤 숫자를 잡아 그 숫자가 포함된 조건을 모두 제거해 주고 재귀를 합니다. 이후에는 조건 중 절반 이상을 만족하는 위치에 배치하면 됩니다.

 

7/15 화요일

34062 Distance Multiplication Maximization: 답의 후보가 되는 점은 지름의 양 끝점이나 경로와 지름의 교선 위 가장 긴 체인의 끝점입니다. 이때 길이를 고정하면 이분탐색으로 답을 구해줄 수있고 길이의 후보가 최대 $\sqrt N$개이므로 적당히 처리해 줄 수 있습니다. 

 

제9회 천하제일 코딩대회 본선 Open Contest

 

학교 공강시간에 대회가 있길래 참여했고 6솔로 4등을 했습니다. 

 

34063 OPS 분석: E, F를 고정한 뒤 2차원 DP

34064 밤(Time For The Moon Night): BFS + 유파

34065 공통 순서쌍 찾기: 한 순열을 $1,2,\dots,N$으로 바꿔준 뒤 셋을 이용하여 인버젼 쌍 찾기

34068 오디션: 정렬 후 적당한 그리디

34069 자리 바꾸기: 행이나 열 중 하나가 짝수면 자명, 아니면 불가능

34071 첫 번째 문제는 정말 쉬운 문제일까?

 

7/17 목요일

The 2022 ICPC Asia Seoul Regional Contest

H는 버추얼 끝나고 풀었습니다

 

realpsdoingdamyoo와 함께 버추얼을 했습니다.
5시간 동안 9솔을 했고요 2인 2컴으로 참가해 다른 팀과 직접 비교는 어렵지만 괜찮게 했습니다.
일단 제가 G~L을 봤고 I, J, K를 쉽게 푼 뒤 L을 대략적인 풀이를 냈다가 유담이와 함께 고민해서 맞는 풀이를 만들고 짜서 냈습니다.
유담이가 A, F를 AC받고 C를 푸는 동안 제가 D, E를 풀었습니다.
결과적으로 제가 6솔을 했고 유담이는 3솔을 했지만 무려 다이아를 2개나 풀었어요.
H 풀이를 빨리 찾고도 구현과 디버깅에 2시간이라는 많은 시간을 쏟은 점, 쉬운 문제에서 쓸데없는 WA를 낸 점에서 풀이를 최대한 구체화한 뒤 구현하는 게 필요해 보입니다!!

 

26105 Folding Stick: DP를 짜고 세그로 최적화

26106 Forbidden Turns: 간선을 정점으로 한 다익스트라

26109 Longest Substring: 접미사 트리 + 큰작 + 그리디 + 셋질을 하면 됩니다. 이 문제가 제 첫 접미사 트리였는데 접미사 트리의 발상과 구현을 자력으로 했어요!

26110 Palindrome Type: 재귀

26111 Parentheses Tree

26112 Shuffle Game: 3차원 LCS DP

26113 Two Choreographies: 정점이 $N$개고 간선이 $2N-3$개이면서 직선이 아니면 비둘기집의 원리에 의해 깊이 차가 동일한 백 엣지가 무조건 존재합니다. 직선인 경우에는 모든 깊이 차의 백엣지가 존재하므로 항상 $3$개의 정점을 포함한 사이클을 $2$개 만들 수 있습니다. 컴포넌트가 여러 개 나뉘는 경우 정점이 $V$개고 간선이 $2V-3$ 초과인 컴포넌트가 무조건 존재하므로 동일하게 해결할 수 있습니다.

 

7/18 금요일

33256 Toy Marbles: 그래프 구성 후 사이클 유지한 채로 잘 옮겨주기

23067 Tortoise: 개어려워요

 

셋을 돌았어요!

 

7/19 토요일

11667 생산성 향상: 어떤 구간을 포함하는 구간을 모두 제거하면 단조성 있는 상태가 되고 거기서 DP

 

검수를 했어요!

 

Order Capital Round 1 (Codeforces Round 1038, Div. 1 + Div. 2)

D에서 2틀 박고 내 풀이가 아예 틀렸음을 깨닫고 E를 갔으나 구현을 개같이 못해서 3솔로 끝냈습니다.

 

7/20 일요일

정올 2차 날이지만 미국을 갔지요