dlwocks31의 PS일기장

올해는 병특으로 근무중이여서 재학생이 아니기 때문에 어처피 본선은 못 나가고, 작년 Little Piplup 팀에서 나랑 같은 휴학생 처지가 된 Coffeetea, Diordhd와 한 팀을 꾸려서 나가게 되었다. 결과는 생각보다 괜찮았던 7솔브! 비록 A랑 J가 풀만했지만 풀지 못했던 게 조금 아쉽긴 해도, 대회 중에 문제 솔루션이 끊임없이 나왔고, 구현도 큰 코딩 실수 없이 생각했던 걸 (J 빼고) 모두 빠르게 구현해내서 좋은 결과를 얻을 수 있었던 것 같다. 대회 중 역할분담은 주로 Coffeetea와 Diordhd가 솔루션을 생각해서 전달해주고, 그걸 내가 받아서 구현하는 방식이였다. 우리가 푼 문제 한정으로 솔루션은 koosaga.com/262 와 대략적으로 일치해서, 여기서는 솔루션을 자세하기 ..

정말 오랜만에 하루종일 PS했다. 결과는 그렇게 맘에 들지는 않지만, 그래도 오랜만에 PS를 스릴있게 한 것 같다.다만 1년 전과 달리 실력이 별로 늘어난 느낌이 들지 않아서 좀 슬펐다. 1년 전에는 지금의 나는 SCPC예선쯤은 여유롭게 통과할 줄 알았는데, 역시 지난 1년간 PS 열심히 안한게 티난다..ㅋㅋㅋ 매우 아슬아슬한 점수인데 과연 본선 진출할 수 있을까? 1 - 실력 맞추기 (13:10 AC) 일단 두 개의 같은 길이의 배열 \(a_i\), \(b_j\)가 있고 1:1매칭을 해서 \(abs(a_i - b_j)\) 의 합을 최소화하는 문제인데, 대신 하나의 \(a_i\)를 임의의 숫자로 수정할 수 있는 문제이다. 기본적으로 아무 수정을 하지 않는다면 그냥 정렬하고 같은 인덱스끼리 매칭하면 되는데..

https://www.acmicpc.net/category/detail/2054 UCPC 2019 www.acmicpc.net 17등! 개인적으로는 그냥 딱 우리 실력에 풀 수 있는 걸 다 푼 느낌이였는데 생각보다 높은 순위를 받았다. 이번 셋이 워낙에 어려웠고 5솔 표준 세트였던 ABEKL중에서 A, E가 정말 말리기 쉬운 문제였기 때문에 그런 듯 하다. 타임라인: 0분: 시작할 때 gyuni가 ABCD, 내가 EFGH, nevivurn이 IJKL을 맡기로 했다. 우선 난 E의 페이지수를 보고 바로 빡구현문제라 판단해 일단 넘어갔고, F는 미친기하의 냄새가 나서 도망갔다. 7분: (현장 사진)"어 이거 그냥 트리 대충 그어보면 나오지 않을까?" 하고 G번에 뭔갈 적고 있는 dlwocks31. 아니였다고..

아직 병특 3년+학교 2년이 남아 있어 SCPC에 올해 빼고도 5번은 더 참가할 수 있는데 수상기회는 2번밖에 없어 그냥 최대한 편하게 할려고 했다. 상 탈 수 있으면 좋은거고 못타면 내년에 더 잘할 때 더 좋은 상 타는거고.. 결과적으로는 616점으로 커트라인에 걸려서 바라는 대로 수상하지 못했다(?). 내년을 노린다..! A - 예선 A번으로 나왔어도 적당한 난이도 같다. 딱히 할 말은 없다. B - 좌표평면에 점들이 주어지고 그 점들을 잘 이어 단순다각형을 만드는데 그 단순다각형의 둘레를 최대한 크게 만드는 최적화 문제. 나는 컨벡스헐 만들때 쓰는 그 좌표정렬을 하고 순서대로 이어서 193점을 받았다. 공식 풀이가 꽤 재미있었는데, lower convex hull을 하나 만들고 남은 점들을 x좌표가..

문제 - https://www.acmicpc.net/category/detail/2053 최종 스코어보드 - https://ucpc.acmicpc.net/contest/spotboard/449 I HATE PS★팀으로 UCPC예선에 참가해 38등으로 본선진출에 성공했다! 대충 우리 팀이 뭘 했는지 30분 간격으로 기억나는대로 적어보겠다. 0-30분: A 9분 AC - gyuni가 시작하면서 읽고 바로 풀어냈다. B 18분 AC - 내가 읽고 바로 풀었다. 밀면서 좌표가 어떻게 매핑되는지 헷갈려서 살짝 헤맸지만.. 종이에 정리를 잘 하고 풀자! 그 후 E, F, C번 정도를 읽어봤는데 잘 모르겠어서 넘겼다. 30-60분: gyuni가 나한데 D번이 풀만한거 같다며 넘겨줬고, 나는 다소 해메다가 [해석할려는..

https://codeforces.com/contest/1197/standings/participant/26546079#p26546079 일단 오렌지 복귀는 했으니 잘한걸로..? A. DIY Wooden Ladder 가장 큰 두개를 수직선으로 삼으면 된다. B. Pillars max에서 시작해서 투포인터로 퍼저나가는 방법을 썼다. maximum이 global maximum인지 확인하는 방법이 더 좋고 편한 방법같다. n-1을 찾고 - n-2를 찾고 - ...식으로 생각해서 이런 풀이가 나왔던거 같다. 쉬운 문제여서 다행히 큰 상관은 없었다. C. Array Splitting 처음에 a_i >= a_i-1를 못보고 whining하고있었다. 조건을 잘 읽자.. division하는 operation이 cost..

https://codeforces.com/contest/1178/standings/participant/26499798#p26499798 결과적으로는 만족스러운 라운드였다. :) A. Prime Minister 그리디하게 가져올 수 있는 파티를 다 가져오면 된다. A번치고 문제가 길어서 읽기 힘들었다. B. WOW Factor o하나당 (좌측에 있는 w개수*우측에 있는 w개수)를 더하면 되고 왼쪽에서 오른쪽으로 순차적으로 보며 카운트를 잘 관리하는 식으로 O(n)에 풀 수 있다. C. Tiles 대회 중에는 처음에는 dp쪽으로 생각해보다가, 예제를 보고 2**(w+h)라는 식을 찍어서 냈고 맞았다.이 식이 맞다고 확신한 결정적 계기는 14분여쯤에 맞은 사람 수를 봤는데 200명이 좀 넘었다. 정말 dp였..

https://codeforces.com/contest/1195 Dashboard - Codeforces Round #574 (Div. 2) - Codeforces codeforces.com 스코어보드에 대조해 보니 대략 2070점 정도의 퍼포먼스로 보인다. 오늘 라운드도 어김없이 뇌절이 넘쳐났다. 전체적으로 실수가 좀 적었으면 좋겠다.. A: 처음부터 알고리즘은 맞았는데 n과 k헷갈려서 AC가 32분 늦어졌다. 그리고 33분 제출에서 test 17에 틀렸는데 이건 pretest에 없었기 때문에 내가 실제로 대회에 이대로 나갔으면 시스페일이였을 것이다... B: 곱셈 오버플로우때문에 한번 틀리고 시간복잡도 문제인줄 알고 binary search로 다시 써서 맞췄다. C: 간단한 DP. D: 길이 X와 길..