leo020630의 블로그

쓸 내용이 많이 없어 간략히만 적도록 하겠다. 타임라인 ~0:44 여느 년도와 마찬가지로 1번은 꼭 풀고 가야 할 문제라고 생각해 우선 1번을 열심히 풀었다. 풀이는 잘은 기억나지 않지만 변수 분리를 해 set으로 잘 관리해주면 풀 수 있었던 것 같다. ~0:56 이후 2번을 봤는데, 풀테는 잘 모르겠고 우선 \(O(N^3)\) 섭테 먼저 긁었다. 이후 이상한 최적화를 몇 번 하다 3번으로 넘어갔다. ~1:22 3번을 좀 생각했는데 2번 섭테부터는 시간이 좀 필요할 것 같아 1번만 긁고 다시 2번으로 돌아갔다. ~4:00 4번, 5번도 잠깐 봤지만 별 생각이 안나 다시 2번으로 돌아왔다. 2시간 반 쯤 지났을 때 2번의 핵심적인 관찰 하나를 해냈고, 세그트리를 \(N\)개 만들면 \(O(N^2 logN)..

이번 여름 4연속으로 있는 대회 운영의 2번째 타자인 SUAPC가 종료되었다. 저번 DKSH 대회 후기에는 3연속이라고 썼었는데, 그 사이 하나가 늘었다. 꽤 긴 시간동안 준비했기에, 후기를 좀 더 상세히 써 보려 한다. 대회 링크 : https://www.acmicpc.net/category/detail/3180 발단 이후 더 자세히 말하겠지만, PPC와 다른 대회들 준비를 위해 2월부터 만들어 둔 문제들이 조금 있었다. 하지만 교내대회에 쓰기 부적합하거나, 비슷한 문제가 큐에 있어 기각된 문제들이 꽤 생겨버렸다. 이를 어디 쓸지 고민하던 중, 내가 알기로는 유이하게 Call for Task를 받는 대회인 SUAPC에 문제들을 냈다. 총 6개 정도를 냈는데, 3개는 전형적이라는 이유로, 1개는 풀이가 ..

지난 포스트에서 글을 자주 쓰겠다고 했는데, 바쁘다고 미루다 보니 또 2주동안 글을 쓰지 않았다. 그동안 있던 SCPC 본선과 SUAPC는 별도의 글을 올릴 예정이다. 2주동안 있었던 코포랑 앳코더는 다 언레라 진지하게 치지 않아서 여기 올리기엔 좀 그런 것 같아 백준에서 푼 문제들만 정리해보려 한다. 2021 홍익대학교 프로그래밍 경진대회 23320 홍익 절대평가 그냥 구현. 문제가 친절해서 실수도 필요 없고 정렬도 필요 없다. 23321 홍익 댄스파티 그냥 구현. 귀엽긴 한데 무슨 말인지 알아보기가 좀 힘들었다. 23322 초콜릿 뺏어 먹기 코포식 그리디 문제이다. 풀이는 자명하게 찾을 수 있다. 23323 황소 다마고치 역시 코포식 그리디 문제이다. 어느 경우가 최적인지는 잘 생각해보면 알 수 있고..

블로그를 너무 방치해 둔 것 같아 오늘의 PS 글을 하루에 하나는 아니더라도, 일주일에 하나 정도는 써보려고 한다. UCPC가 끝난 이후부터는 개인 PS 공부를 정말 거의 하지 않아서 쓸 내용이 없었지만, 그래도 이번주부터는 뭐라도 해보려고 한다. SCPC 대비도 해야 하고.. 이번주에는 백준에서 셋 2개정도를 풀고, 코포 1번과 앳코더 2번을 쳤다. 코포는 2번이 더 있었으나 노느라 치지 못했고, 앳코더는 두 번 모두 쳤다. BOJ 화요일에는 동아리 연습용 셋으로 던져 놓은 2021 IUPC 를 풀었다. 마지막 문제 빼고는 모두 화요일에 풀었고, 마지막 문제는 귀찮아서 미루다가 오늘 풀었다. 23080 스키테일 암호 브론즈 문제이다. 잘 구현해주면 된다. 23081 오델로 실버 구현 문제인데, 제한이 ..

이번 여름 3연속으로 있는 대회 운영 참여의 첫 타자인 DKSH 대회가 종료되었다. 검수진 모집은 6월쯤에 진행되었던 것 같고, 몇몇 문제는 먼저 완성되기도 했지만 본격적인 검수가 시작된 것은 열흘 전이다. 검수를 할 시간도 촉박했고, 검수진들의 수도 적고 한 분은 IOI로 해당 기간 내내 바쁘셔서 제대로 된 확인이 되지 않았던 것 같다. 시간이 많이 없었기 때문에, 나는 셋의 퀄리티를 뜯어고치기보다는 맞는 풀이 내보고, 지문 수정에 힘썼다. (반응을 보니 아마도 이는 틀린 선택이었던 것 같다) 거의 모든 지문을 한번씩 뜯어고쳤고, 입출력 / 서브태스크 / TeX 형식까지 맞춰주었다. 그럼에도 확인 못한 부분이 생긴 것은 내 불찰이 맞는 것 같다. 아마 풀이를 대강 아는 입장에서 수정해서 푸는 사람의 입..

[1차 예선] 1차 예선은 커트라인이 널널하다는 사실을 알고 있어서 적당히만 풀었습니다. 풀이는 기억도 잘 나지 않을 뿐더러 잘 설명한 좋은 글들이 많기 때문에 생략하겠습니다. [2차 예선] 그리고 오늘 2차 예선이 진행되었습니다. 대략적인 타임라인을 기술해보도록 하겠습니다. ~00:10 1번은 적당히 쉬운 것 같아서 바로 풀었습니다. 최소 횟수는 직관적으로 구할 수 있고, 비용 역시 k보다 작은 수가 등장하는 구간의 길이를 잘 관리해주면 구할 수 있습니다. 저는 pq+set을 사용했습니다. ~00:34 2번도 빠른 시간 내에 풀었습니다. 같은 반인 학생끼리는 가장 밖부터 묶어주는 것이 최적임을 알 수 있습니다. 이를 반복하면 여러 개의 구간을 얻을 수 있는데, 모든 구간의 길이의 합에서 겹치는 구간 쌍..

5솔브, 27등으로 대회를 마쳤습니다. 타임라인 ~0:16 제가 앞, slah007 선배가 가운데, qjatn0120 선배가 뒤를 보고 시작했습니다. 두 선배는 각각 쉬운 H, J를 빠르게 밀었고, 저는 그나마 할 만 해보인 C를 잡았습니다. ~0:58 이후 L의 WA가 몇 번 나온 후 AC가 나왔습니다. 저는 C를 끄적이고 있었고, slah007 선배는 제가 준 D를 잡았습니다. ~2:33 C는 저와 qjatn0120 선배가 무수히 사풀을 만들어내고 있었고, slah007 선배는 묵묵히 D를 잡아 AC를 띄웠습니다. 40%쯤에서 한번 틀렸는데, 코드에 Q가 하나도 보이지 않길래 제가 지적했더니 오타라고 하면서 바로 맞았습니다. ~4:45 이후 qjatn0120 선배는 C를 버리지 못하고 계속 잡다 F로..

오랜만에 언레로 치는 Div. 2이다. 언레라 좀 중간중간 놀면서 쳤다.. A. Three Doors (0:04, +) 경우를 잘 나누어주자. B. Also Try Minecraft (0:12, +) 양 방향으로의 누적합 배열을 만들어주면 쉽게 해결할 수 있다. C. Recover an RBS (0:20, +) 만약 만드는 방법이 유일하다면 ?인 자리에 대해서 (((..))) 형태일 것이다. 괄호 문자열의 조건 상, 가장 안전한 다음 해는 (((..)(..)) 형태일 것이기 때문에 이 형태의 해를 만든 후 괄호 문자열인지 판별해 주면 된다. 인덱싱 실수로 한 번 틀렸다. D. Rororobot (0:31, +) 만약 x좌표의 차이나 y좌표의 차이가 k로 나누어떨어지지 않으면 불가능하다. 이 조건을 통과한..

A. Another String Minimization Problem (0:04, +) 그리디하게 잘 바꿔주면 된다. 평소 A보다는 살짝 어려웠던 듯 B. Making Towers (0:13, +) 각 칸 사이에 짝수 개의 원소가 있어야 = 인덱스의 홀짝성이 계속 바뀌어야 탑을 쌓을 수 있다. 이를 바탕으로 잘 구현해주면 된다. 별로 맘에 드는 문제는 아니었다. C. Qpwoeirut And The City (0:22, +) 원소가 홀수개일때는 배치가 결정되지만, 짝수개라면 중간에 한 칸을 띄울 수 있다. 두 경우에 대한 prefix sum을 미리 계산해준 후 어디서 띄울 지를 결정해주면 된다. D1. Chopping Carrots (0:34, +) MAX를 고정하면 만들 수 있는 수 중 해당 값에 가장..

A. A Unique Letter (0:01, +) *12 ABC A답게 잘 구현해주면 된다. B. Better Students Are Needed! (0:06, +) *195 B치고 꽤 복잡했다. 구조체를 만든 후 3번을 잘 정렬해주면 문제를 해결할 수 있다. C. Changing Jewels (0:13, +1) *413 뭔가 복잡한 연산이 쓰여 있는 것 같지만, 그리 어렵지 않다. 제한이 매우 작기 때문에 대충 시뮬레이션 해주면 된다. D. Draw Your Cards (0:22, +) *1074 (가장 위 수, 쌓인 개수)를 원소로 하는 pair형 set을 사용해주면 적절한 구현으로 문제를 해결할 수 있다. 각 원소마다 내 밑의 원소를 저장해주면 답 계산도 편하게 할 수 있다. E. At Least..