leo020630의 블로그

HeeJaYaa님의 추천으로 Class 9 문제들을 풀고 있다. Class 9 문제들은 인터넷에 풀이가 많지 않은 경우가 꽤 있어 푸는대로 풀이를 작성해보려 한다. 원래 어제부터 풀고 싶던 문제는 https://www.acmicpc.net/problem/9244 인데, 하루동안 생각해도 모르겠어서 넘어왔다. 혹시 저 문제 푸신 분 있으면 힌트 부탁드립니다.. 문제 요약 숫자로 이루어진 문자열이 주어질 때, 다음과 같은 두 쿼리를 처리해야 한다. 1번 쿼리 : 구간 \([l, r]\)에 위치한 숫자 \(x\)를 모두 \(y\)로 바꾼다. 2번 쿼리 : 구간 \([l,r]\)을 읽은 수를 998244353으로 나눈 나머지를 출력한다. 풀이 일단 업데이트 쿼리가 없다고 생각해보자. 그러면 세그트리의 각 노드에..

A. Equal Hamming Distances (0:04, +) *357 케이스를 나눠준 후 그리디하게 처리해주면 된다. 두 수가 같을 때는 무조건 0, 다를 때는 횟수를 잘 세며 최대한 0부터 써주면 된다. B. A < AP (0:19, +) *1333 앞에서부터 보면서 Union Find로 연결하며 개수를 잘 세면 되는데, 정해는 이렇게 복잡한 방법으로 할 필요 없이 대칭성을 이용하는 것이었다. C. 01 Game (0:48, +) *1940 케이스를 잘 분석해주면 각 상황에서의 그런디 수를 구할 수 있다. 양 끝이 같은 수인 경우 1, 다른 수인 경우 0, 한쪽 끝이 막혀있는 경우 칸 수, 두 끝이 막혀있는 경우 칸 수의 홀짝성이 그런디 수가 된다. 그대로 스프라그 그런디 정리를 적용해주면 된다...

하루에 대회 3개를 쳤기 때문에 묶어서 정리하려고 한다. BOJ - 초콜릿컵 A. 초콜릿 피라미드 (0:12, +) 차분히 식정리를 해주면 된다. B. 초콜릿과 나이트 게임 (0:32, +) \(XY=0\)인 경우, \(X=Y\)인 경우, 그 외의 경우로 나뉜다. 앞 두 케이스는 7번, 뒤 케이스는 15번만에 게임을 끝낼 수 있다. 구현이 좀 귀찮은데, 난 그냥 cout을 29개 썼다. C. 예쁜 초콜릿과 숫자놀이 (1:51, +3) 제한이 애매하게 커서 완탐도 안될 것 같고(사실 된다), \(O(N^2 MOD)\) DP는 생각이 나지 않아 그냥 \(O(N^3 MOD)\) DP에 비트셋을 박았다. 왠지는 모르겠지만 실행시간 1등이다. 비트셋 최고 D. 초콜릿 나눠 팔기 (2:09, +) 케이스를 나누면 ..

A. Make A Equal to B (0:02, +2) 적당히 케이스워크를 잘 해주면 된다. 난 완전히 같을 때, 구성만 같을 때, 그렇지 않을 때로 분류하였다. B. Playing with GCD (0:42, +5) \(B_i\)는 \(lcm(A_{i-1}, A_i)\)일 때가 최적이다. 따라서 이를 만들어준 후 확인해주면 된다. 나는 이상하게 해서 많이 틀렸다. C. Good Subarrays (0:28, +1) 투포인터처럼 생각해주면서 잘 구현해주면 된다. C2는 좀 봤는데 모르겠어서 넘어갔다. D. Equal Binary Subsequences (0:55, +) 뭔가 어렵게 생긴 조건인데, 이게 Div. 2 D라는 것과 코포라는 점을 생각하며 가장 쉬운 풀이를 찾아보자. 똑같게 나눌 수 있는 가..

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) 수가 무엇인지는 중요하지 않고 홀짝성만이 중요하다. 제한이 작으므로 홀수의 개수와 짝수의..

https://leo630.tistory.com/92 이 글에서 이전 년도 PPC 문제들 풀이를 작성하기로 했었는데, 올해 대회가 3일 후이기 때문에 우선은 2018년도 대회 풀이를 써보려 한다. 2019년 대회는 쓰지 않을 예정인데, 아직 다 풀지도 않았고 + 뭔가..뭔가인 문제들이 좀 있고 + 무엇보다 에디토리얼이 있길래 생략하도록 하겠다. 우리 학교 대회인 만큼 평소 쓰던 풀이들보다는 정성들여 써보도록 하겠다. A. Caesar Cipher 문제 소재로 자주 등장하는 카이사르 암호인데, 다른 문제들에 비해 까다로운 부분이 몇 군데 있다. 1. $k$의 크기가 크다. 이는 어떤 알파벳을 26번 밀면 다시 돌아온다는 것을 이용해, $k$를 26으로 나눈 나머지를 취한 후 진행해도 똑같은 결과를 얻을 수..

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