leo020630의 블로그

A. Continuous 1 (1:50, +7) *952 앳코더에서 뭐 이런게 나오지? 싶었다. 역시 나답게 케이스워크를 환상적으로 한 후 결국 1시간쯤에 B로 넘어갔다. B 풀고 난 후 돌아오니 반례가 보여 고쳐서 맞았다. B. Better Students Are Needed! (0:06, +) *1466 시간이 꽤 지나 풀이가 구체적으로 기억나진 않지만, 식 정리를 잘 하면 가능한 비율로 $\lfloor \frac{B}{i} \rfloor$ 꼴만 봐도 되었던 것 같다. 저 꼴에서 나오는 서로 다른 수의 개수가 $O(\sqrt{N})$임은 이제 유명하다. A에서 1시간+a를 쓴 결과 블루로 다이빙했다.

A. Ela Sorting Books (0:15, +2) 각 묶음에 대해 Mex 이후로는 무슨 알파벳이 들어오던 상관이 없다. 따라서 앞 묶음부터 앞 알파벳을 하나씩 넣어주는 것이 항상 최적이다. 구현을 약간 이상하게 해 2번 틀려서 B 풀고 다시 와서 풀었다. B. Ela's Fitness and the Luxury Number (0:13, +) 각 $a$에 대해 $\lfloor\sqrt{x}\rfloor = a$인 $x$ 중 $a$의 배수는 3개 $(a^2, a^2+a, a^2+2a)$이다. 이 사실을 이용해 잘 구해주면 된다. sqrt 함수를 쓰면 틀린다는 얘기가 많은데, 나는 그냥 맞았다.. 왜지? C. Ela and Crickets (0:42, +2) 대충 해보면, 우물 정..

주말에 노느라 ABC, ARC를 다 안쳐서 죄책감에 이거라도 쳤다. A. Working Week (0:12, +) 잘 정리하면 답은 $\frac{n}{3} - 2$라고 한다. 난 생각이 안나서 더럽게 풀었다. 이걸 어떻게 알지? B. Tea with Tangerines (0:16, +) 최솟값이 기준이 되어야 한다는 사실을 자명하게 알 수 있고, 다른 수들도 잘 나눠줄 수 있다는 사실은 덜 자명하지만 찍어서 맞출 수 있다. C. Phase Shift (0:35, +1) 그리디하게 보내주면 되는데, 모든 알파벳이 반드시 하나의 큰 사이클을 이루어야 해서 좀 까다롭다. 난 대충 Union Find를 써서 구현했다. D. Meta-set (0:47, +) 2개를 정하면 남은 1개를 정할 수 있다. 따라서,..

팀 연습이 끝나고 Rated 코포가 있길래 오랜만에 쳤다. A. Glory Addicts (0:06, +) 잘 번갈아서 하는 것이 최적이다. 정렬한 후 큰 것 부터 써주면 되는데, A번 치고 케이스 워크가 좀 있는 편이라 어려웠다. B. Prefix Sum Addicts (0:14, +) $N=K$일 때는 배열을 만들 수 있으므로 단조증가인지 판별하면 되고, $K=1$일 때는 항상 가능하다.이를 잘 접목하면 그렇지 않은 상황에서도 만들어진 배열이 단조증가인지 판별하고, 만들어진 배열의 첫 항을 잘 만들 수 있는지 판별하면 된다는 사실을 알 수 있다. C. Even Number Addicts (0:38, +1) 수가 무엇인지는 중요하지 않고 홀짝성만이 중요하다. 제한이 작으므로 홀수의 개수와 짝수의..

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

굉장히 오랜만에 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..

A. Subtle Substring Subtraction (00:04, +) 평소 A치고 어려웠다. 문자열의 길이가 짝수면 자명하게 선공이 다 지울 수 있고, 홀수라면 첫 글자를 남기거나 마지막 글자를 남기는 것이 최적이다. B. A Perfectly Balanced String? (00:14, +) B답게 쉬울 것 같아서 적당히 찍었더니 맞았다. 내가 한 가정은 '두 같은 알파벳 사이에 다른 모든 알파벳이 최소 하나씩은 있어야 한다' 이다. C. Palindrome Basis (00:18, +1) 팰린드롬의 수가 적당히 작기 때문에 $O(NM)$에 냅색을 써주면 풀 수 있다. D. Lost Arithmetic Progression (01:18, +1) 우선 예외 케이스를 잘 분석해서 0, -1에 대..

A. Red Versus Blue (0:02, +) R/(B+1)개와 R/(B+1)+1개를 적절히 배치해주면 된다. B. Bit Flipping (0:16, +) 앞에서부터 그리디하게 설정해주면 되는데.. 구현 미스가 나서 좀 오래 걸렸다. C. Line Empire (0:40, +) 끝 위치가 $x$라면, 그 전까지는 계속 옮겨주는 것이 최적이다. 이를 각 경우에 대해 계산해주면 된다. D. Reverse Sort Sum (1:06, +) 우선 주어진 배열의 평균을 통해 1의 개수를 구해준다. 이후, 뒤 원소부터 보며 자명하게 결정 -> 1의 개수에 따라 업데이트를 반복해주면 문제를 해결할 수 있다. Range Update Point Query 펜윅트리를 사용하면 $O(NlogN)$에 문제를 해..