본문 바로가기

PS

USACO 2020 January Gold 업솔빙 후기

아마 한동안은 끌리는 문제 풀지 않을까.

쉽게 질려하는 내 성격에 문제집 하나 계속 푸는 건 솔직히 힘들었다.

 

골1 / 플5 / 플2 이렇게 세 문제로 이루어져 있는 세트이다.

한 문제 쉽고, 한 문제 확률적으로 풀 수 있을 거 같고, 한 문제는 어렵게 느껴질, 상당히 내 실력에 적합한 세트라고 생각했다.

 

공식 테스트케이스와 영어로 된 솔루션은 이 링크에 있다.

http://usaco.org/index.php?page=jan20results

----------------------------------------------------------------------------------------

#18316 Time is Mooney

DP문제이다. T변화량이 (T+1)^2-T^2이라 선형적인데

m[i]<=1000이라는 점에서 T가 500 이상으로 커지지 않는다는 점만 눈치채면 된다.

-----------------------------------------------------------------------------------------

#18317 Farmer John Solves 3SUM

처음엔 N^3lgN으로 풀고 모르겠어서 답봤다.

N^2lgN로 푸는 방식도 있다. value<=10^6이라는 점을 이용해서 value별로 벡터를 구성/정렬해주고, lgN만에 upper_bound와 lower_bound로 답을 더해주는 방식이다.

정해인 N^2풀이는 마찬가지로 value<=10^6이라는 점을 이용해서 각 j에 대해 등장한 value를 선형적으로 처리한다.

즉, sum[i][j]+=cnt[-a[i]-a[j]], cnt[a[j]]++ 의 과정으로 처리한다. 저거 그냥 구현하면 안되고(음수 인덱스) 10^6만큼 더해서 인덱스를 처리한다.

-------------------------------------------------------------------------------------------

#18318 Spring Boards

와 solved.ac 플2!! 답봤는데도 이해하기 정말정말 많이많이 힘들었다.

대강 풀이가 다음과 같다.

 

시작점 끝점 x축으로 정렬하고 처리한다.

처리하면서 y축으로 정렬된 상태에서 단축 거리를 관리하는 map을 이용한다.

 

코드 보며 이해했었는데, 구현해봤자 방금 외운거 그대로 짜는 기분일 거 같아서 굳이 안했다.

이렇게 솔브드 랭킹 올리고 싶진 않았다.

 

그래도 map iterator 쓰는 건 연습해야하기에 3-7일 뒤에 좀 쿨 돌고 짜볼 것 같다.

 

업솔빙....한 거 맞나...? 약간 버거운 라운드였는데, 그래도 이정도가 딱 적당한 것 같다.