다이아 스트릭 (3)
3주간 고통받으며 이었던 스트릭 그중 마지막 주에 푼 문제들이다.
※ 풀이 스포 주의
5/4) 14636번 [Money for Nothing]
예전에 분할정복을 이용한 dp 최적화에 관한 글을 보고 나서 언젠가 한번 써보고 싶다는 생각을 했다. 감소하는 형태의 두 후보군을 처리할 방법을 고민하다 dnc opt에서 나오는 특수한 형태를 만족함을 발견했고 아이디어만 알고 있던 상태라 구현이 이게 맞나 하면서 짰는데 맞았다.
5/5) 28207번 [Classical Geometry Problem]
문제를 공간에 나타내면 정육면체의 각 꼭짓점방향으로 원하는만큼 이동시켜 특정 위치로 이동시켜야 하는 문제다. 2차원으로 낮춰 생각해봤을때 오른쪽 위 꼭짓점을 마지막으로 사용해 이동시키고자 하면 그 전에 제시한 위치와 오른쪽위 꼭짓점을 지나는 직선위에 점이 위치하면 된다. 가장 만들기 쉬운 아랫변과 왼쪽변 둘중 교점이 존재하는 점까지 이동시키는것이다. 이제 원래 문제로 돌아오면 평면위 한점에 위치시키는 방법을 알고있으므로 같은 방법으로 (255,255,255)와 제시한 위치를 지나는 직선과 xy,yz,zx평면 셋중 하나와의 교점을 찾아내면 된다.
5/6) 15310번 [아티스트]
문제만 보면 간단히 해결할 수 있는 아이디어가 뭔가 있을것 같은데 도저히 떠올리지 못해서 결국 에디토리얼을 깠고 너무 아이디어가 아름다워서 그냥 하루종일 여운에 잠겨 어떻게 이런 아이디어를 떠올릴수 있지 머리속으로 nmk번 반복하면서 하루를 보냈다. 이때는 분할정복 풀이를 완전히 이해하지 못해 불도저로 풀었고 나중에 timeismoney 풀이를 떠올리다 분할정복 풀이를 깨달았다.
5/7) 27714번 [Klingon High Council Training]
모 실버 문제에 의해 네개의 제곱수로 모든 수를 만들수 있다는 사실은 ps러들에게 잘 알려져 있으나 세개의 제곱수로 표현할 수 있는 수를 찾는것은 쉽지 않았고 검색을 통해 4^a(8b+7)형태를 제외하고 전부 표현할수 있다는 사실을 쉽게 알아낼 수 있었다. 이제 남은건 n개의 더미중 최대 k개의 더미에서 돌을 자유롭게 가져올수 있는 님게임을 푸는것인데 이것도 고민해보다 검색을 해봤고 관련된 글을 찾을 수 있었다. 각 비트의 sum이 k+1로 나눠 떨어지면 후공이 승리한다. k=1일때 xor이랑 결론 같은거 보고 좀 충격이였다.
수직 이등분선을 기준으로 반평면을 삽입해 나가며 넓이를 계산하는 문제다. 제한이 작아 각 때마다 반평면 교집합을 전부 계산해줘도 충분하다.
무게중심을 포함하는 삼각형의 개수를 세면 된다. 정수 좌표 꼭짓점을 가지는 다각형의 무게중심*6이 정수임을 이용하면 실수 오차로 고통받지 않아도 된다. 무게중심은 가중평균으로 구할수 있고 삼각형의 개수는 각도정렬+투포인터로 구할 수 있다. 무게중심을 구하는 기본적인 문제는 p3으로 매겨져 있고 원점을 포함하는 삼각형의 개수를 세는 문제가 p2로 매겨져 있어 확실하게 다상위는 아닌것같아 하향기여를 했다.
5/10) 30149번 [Animesh decides to settle down]
n<=30짜리 귀여운 반평면 교집합 문제다
날먹문제를 끝으로 처음엔 예상도 하지 못했던 21일의 스트릭이 끝났다 ㅋㅋ
하면서 삶이 피폐해지는걸 체감했는데 다시는 이런짓 안할거다
Comments
Post a Comment