leo020630의 블로그

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

오랜만에 언레로 치는 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..

ARC랑 코포 Div.1을 쳤다. ARC 144 A. Digit Sum of 2x (0:04, +) *105 우선 111..11 식으로 배치하면 첫번째 답은 \(2N\)임을 자명하게 알 수 있다. 이러한 \(x\)는 각 자리수가 4 이하여야 하므로, 4를 최대한 많이 쓰는 식으로 나열해주면 된다. B. Gift Tax (0:19, +) *895 이분 탐색을 이용할 수 있다. \(a

굉장히 오랜만에 CP 카테고리에 글을 쓴다. 오늘의 PS와 경계가 모호해진 것 같긴 하지만, 오늘은 이것 외에 문제풀이 활동을 하지 않아서 그냥 여기 적겠다. ABC 259 A. Growth Record (0:03, +) *34 평소 A번치고 헷갈려서 솔브가 약간 늦었다. 문제는 쉽다. B. Counterclockwise Rotation (0:08, +) *180 이런 걸 왜 내지? 잘 회전변환 해 주면 된다. C. XX to XXX (0:14, +1) *451 두 문자열을 묶음으로 본 후 잘 비교해주면 된다. 인덱싱 실수로 한번 틀렸다. D. Circumferences (0:22, +) *947 이런 걸 왜 내지? 2. 조건에 따라 원들이 겹친다면 Union Find로 묶어주면 된다. E. LCM on..

13:00~15:30 모비스 본선 16:30~18:30? 천코대 오픈콘 23:35~01:35 에듀코포 를 쳤다. 모비스 대회에 대한 후기는 생략하도록 하겠다. 제6회 천하제일 코딩대회 본선 Open Contest 2시간 늦게 참여하기도 했고 중간에 자리를 몇 번 비워서 진지한 마음으로 치지는 않았다. 아마 종료때까지라도 했으면 F는 풀었을 것 같다. A. Gravity Hackenbush 지문 낚시 문제이다. 각 플레이어가 초록색 간선을 최대한 많이 쓰는 것이 최적이므로 이를 토대로 비교해주면 된다. C. Merge the Tree and Sequence Split the SSHS 문제와 세팅이 비슷하다. 간선을 묶는 것은 그때와 같이 하면 되고, 남은 부분은 간선을 묶는 것에 비하면 크게 어렵지 않다...

오늘은 (핸들에서 알 수 있듯이) 생일이었다. 생일이라고 뭔가 거창한 걸 하진 않았고, 그냥 오후에 잠깐 외출 후 돌아와서 지인들과 셋 하나를 돌았다. 셋은 다음과 같다: https://www.acmicpc.net/category/detail/2355 2020 Sogang Programming Contest (Master) www.acmicpc.net 순서를 섞었기 때문에 실제 대회 번호와는 차이가 있다. 우선은 내가 푼 순서대로 정리할 예정이다. 20300 - 서강근육맨 (실제 대회 B, 위 스코어보드에서는 C) A, B가 바로 풀 문제는 아닌 것 같아 C를 잡았다. 짝수일 때는 정렬해준 후 맨 앞과 맨 뒤를 차례대로 매칭해주면 되는데, 홀수일 때는 잘 생각이 나지 않는다. 친절하게도, 제곱 풀이가 가..

어제는 노느라 문제를 풀지 못했다. 오늘은 플레 랜덤 문제를 몇 개 풀었다. 20670 - 미스테리 싸인 볼록다각형 이분탐색 문제를 연습하고 싶어 풀었다. 다각형을 위 아래로 나누는 방법과 각도로 나누는 방법 두 가지가 있는 것 같다. 이거 말고 접선 긋는 문제도 있는데, 한번 연습해 볼 계획이다. 18373 - N!!!...! mod P K가 크면 답이 0이 될 것이라고 추측할 수 있다. 그러면 경우의 수가 몇개 남지 않는데, 이를 열심히 짜주면 시간 초과를 받는다. (12!~=5e8)!을 구하는 게 1초 안에 돌아가지 않는 것 같다. 도저히 모르겠어서 열심히 풀이를 찾았는데, FFT를 쓰는 어려운 풀이와 윌슨 정리라는 걸 쓰는 풀이가 있었다. 티어를 봐선 FFT는 절대 아닌 것 같아서 윌슨 정리를 공..

오늘의 랜덤 검색 태그는 아래와 같았다. 변태라고 생각할 수도 있지만, 그게 아니라 내가 약하다고 생각한 분야를 모았더니 저렇게 됐다. 공평하게 각 태그에서 하나씩 골라서 풀었다. 18862 - 이제 다시 시작이다 기하인 척 하는 자료구조 문제이다. 식 정리를 열심히 하면 넓이를 4가지 경우에 따라 이차함수 꼴으로 계산할 수 있다. 다행히도 좌표의 범위가 주어져 있으니, seg[a]를 \(ex,ey\)와의 거리가 \(a\)인 스피커의 개수로 정의하자. 이러면 4가지 경우의 범위를 잘 나눠준 후 1, \(a\), \(a^2\)의 누적합을 저장하는 펜윅 트리로 답을 구해줄 수 있다. 11406 - 책 구매하기 2 플로우 기본 문제이다. 2814 - 최소인수 기본적인 풀이는 1557번 등과 비슷하다. 이분 탐..