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] 꽤나 고생을 한 문제다. 두 점을 선택해 만들 수 있는 직선 위 선분중 하...

 2달전, 입학하고 한달이 지난 4월, 슬슬 새로운 생활에도 적응하고 많은 사람들과도 알게 되었다. 그리고 뒤쳐지면 안된다는 생각에 시작했던 다이아 스트릭.. 덕분에 3주간 폐인같은 생활을 보냈다. 21일간 기하문제로 다이아 스트릭을 이었고 하루종일 문제 생각만 하면서 지냈다. 그 3주간 풀었던 문제들을 한주씩 정리해보려한다. ※ 풀이 스포 주의 4/20) 3800번 [Art Gallery] 반평면 교집합 기초문제다. 이때까지는 다이아 스트릭을 할 생각도 없었다. 4/21) 22619번 [Voronoi Island] ,  1288번 [전쟁 - 국지전] 각 점에서 다른 점까지 수직이등분선을 경계로 하는 반평면들의 교집합을 구하는 방법으로 naive하게 보로노이 다이어그램을 구할 수 있었다. 4/22) 23194번 [Domes] 두 점을 지나는 직선을 지나면 두 점의 순서가 바뀌는것을 관찰 후 모든 점 쌍에 대해 순서가 올바르도록 하는 반평면 범위의 교집합을 구하면 끝난다. 4/23~24) 1853번 [정사영] , 3873번 [Intersection of Two Prisms] 두 평면에 공통된 축을 기준으로 구분구적법을 이용해 잘게 쪼개 직사각형 넓이를 전부 더해서 구했다. 꼭짓점마다 구간을 나눠 적분하면 좋겠지만 귀찮아서 구분구적법을 썼는데 의외로 오차가 널널해 잘 돌아갔다. 이때부터는 스트릭을 의식하고 있었고 두 문제로 2일의 스트릭을 채웠다. 4/25)  22594번 [Shelter] 보로노이 다이어그램을 구성한 후 각 구역에서 대피소까지 거리제곱의 기댓값을 구하면 되는 문제다. 대피소를 기준으로 다각형을 삼각형으로 쪼개 구하려 했다. 결국 이렇게 삼각 분할을 하여도 미적분 지식 없이 풀지 못한다.. 하지만 위 문제에서 하루의 시간을 더 끈 덕분에 조금 더 생각할 시간이 많았고, 직접 시뮬레이션 돌릴 값을 바탕으로 두 변과 사이각의 각도로 표현 되는 일반항을 찾기 시작했다. 그렇게 생각할 수 있는 모든 형태에서 계수를 비교하...

※풀이과정 스포가 있을 수 있습니다 이번 SAC에서 D,I,J번을 출제했다. D는 관찰이 필요한 간단한 게임이론 문제를, I는 어느정도 차이를 뒤집을 수 있도록 발상, 엣지케이스로 꽤나 시간이 드는 문제를, J는 I와 반대 성격으로 간결하지만 사전지식을 요구하고 실수오차를 신경써야하는 문제를 냈다. 결과는 I,J 온사이트 0제출 ㅋㅋ;; 풀리지 않을 수 있겠다는 생각은 들어도 제출이 안나와서 당황했다. 오픈콘에서는 다행히 두 문제 모두 풀렸다. D번 문제는 이름에 들어간 서로소와 그래프는 딱히 중요하지 않았던 문제다. 같은 연결 요소 위 두 정점쌍을 선택할 수 없다는 사실을 관찰하면 그래프는 의미 없어지고, 모든 케이스가 홀짝홀짝 하는것 밖에 없어서 서로소도 딱히 큰 의미는 없었다. I번 문제는 그냥 공장겜을 하면서 부산물 처리때문에 고생하다 나온 아이디어로 사이클을 어떻게 처리할건지에 대한 아이디어가 핵심이였다고 생각한다. 초안은 공장을 K대 병렬로 설치하는 상황이였지만, 지문이 너무 난해해져 K배 오버클럭을 하는 상황으로 바꾸게 되었다. J번 문제는 파푸스-굴딘 정리를 이용하기 위해 다각형의 무게중심을 구하고 이를 정수 자료형으로 표현해 실수 오차를 줄이는것을 의도하고 만든 문제다...만 검수과정에서 그린정리로 직접 적분하신 분들이 등장하셔서 조금 충격을 받았다. 나름 기하러들을 만족시킬수 있는 문제였다고 생각이 든다. (A,J만 건드린 수상한 사람들이 여럿 보였다.. ㅋㅋ) 첫 출제라 부족한 부분이 많았지만 끝까지 검수해주신 검수진 분들과 온사이트, 오픈콘테스트에 참여해 주신 분들께 감사인사를 드립니다

블로그를 만들었다 사실 전부터 기록용으로 만들려고 했는데 어쩌다 보니 미루고 미뤄져서 지금 만들었다 굳이 이제 와서 블로그를 만든 이유는 최근 뭔가 여러 목표가 한번에 이뤄져서 열정이 좀 식었다 3달만에 다이아/퍼플/1024스트릭을 거의 동시에 클리어 하니까 이후 방향성을 잡기 어려워 나름 생각하고 있었던 목표 중 하나인 블로그를 써보려 한다 굳이 목표를 세우자면 루비/오렌지.. 가 있겠으나 너무 높은 목표라 일단 그 사이 중간 목표를 좀 정해보는 겸 블로그로 동기도 좀 얻으려 생각하고 있다 주된 목적은 아마 문제 풀이 기록, 대회 후기, .. 가 될것같다 블로그 플랫폼은 그냥 글만 쓰기 편해보이는걸로 골랐다 검색 노출이 아쉬울 수 있다는데 기록용이라 그냥 무시하고 음습하게 웅히히거리고 있거라 상관없다 일단 지금은 욕심이 없어서 나중에 욕심이 좀 생기면 옮겨보겠다