taPriS 일기

 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)형태를 제외하고 전부 표현할수 있다는 ...

3주간의 다이아 스트릭중 둘째주에 푼 문제들을 정리해봤다. ※ 풀이 스포 주의 4/27) 3527번 [Jungle Outpost] 문제에서 엄격하게 내부에 존재해야 한다는 조건이 있어 특별한 예외처리 없이 연속된 탑을 폭파했을때 반평면 교집합의 존재여부로 이분 탐색을 하면 된다. 4/28) 3906번 [How I Mathematician Wonder What You Are!] 공선점이 없다는 조건 덕분에 이 문제도 예외처리 없이 반평면 교집합의 존재 여부만 구해주면 된다. 4/29) 9212번 [트라이앵글] 첫번째 삼각형을 포함하는 평면을 기준으로 두번째 삼각형의 세 변과 교점을 구한후 교점이 첫번째 삼각형의 내부,외부 둘다 존재한다면 꼬여있음을 알 수 있다. 4/30)  27861번 [Linked Triangles] 6개의 점을 두 삼각형으로 분할하는 모든 경우를 위 문제와 같은 방법으로 해보면 된다. 문제를 푸는것과는 별개로 일반적인 위치에서 이러한 분할이 항상 존재한다는 사실은 재밌었다. 5/1) 17441번 [파리채 만들기] 이전 글 에서  Shelter(22594번) 을 풀며 삼각형의 한 꼭짓점과 내부 임의의 점까지 거리 제곱의 기댓값을 구하는 방법을 알아냈다. 이번에는 다각형 내부에서 두 점 사이 거리 제곱의 기댓값이다. 미적분학 베이스가 없어 그린정리는 커녕 적분 식 조차 세우지 못하기 때문에 다른 관점으로 생각을 해야했다. 처음 접근은 다각형 내 무게중심과 한 점 사이 거리 제곱 기댓값이 두 점 사이 거리 제곱 기댓값과 동일할 것이라고 직관으로 찍어봤다. 다각형의 무게중심을 구한뒤 삼각형으로 분할해 지난번에 얻은 식을 쓸 수 있었다. 그렇게 구한 값은 원하던 답은 아니였지만 몬테카를로로 구해본 값과 비교했을때 항상 절반으로 나타났고 그대로 두배한값을 내는 코드를 제출해 PBA를 했다. 5/2)  14633번 [Airport Construction] 꽤나 고생을 한 문제다. 두 점을 선택해 만들 수 있는 직선 위 선분중 하...