leo020630의 블로그

하루에 대회 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, +) 케이스를 나누면 ..

셋 : https://www.acmicpc.net/category/detail/1978 내가 뒤, qjatn0120 선배가 앞, slah007 선배가 가운데를 보고 시작했다. ~1:05 나는 I, slah007 선배는 E, qjatn0120 선배는 A를 보고 시작했다. I를 딱 봤는데, 내가 PPC에 낸 신기한 숫자 문제와 상황이 거의 똑같았다. 그래서 바로 짰는데, TLE를 받고 전문 분야인 아호코라식을 잡은 qjan0120 선배에게 키보드를 넘겼다. 허나 바로 되지는 않았고, 그래서 내 J와 qjatn0120 선배의 A가 번갈아서 코딩된 결과 1시간 쯤에 둘 모두 AC를 받았다. ~1:45 이후 I를 보다가, 에라토스테네스 체 두번+포함배제를 잘 쓰면 개수를 셀 수 있을 것 같았다. 그렇게 AC를 받..

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를 쓴 결과 블루로 다이빙했다.

6솔브, 39등으로 대회를 마쳤습니다. 타임라인 자세한 시간대가 생각나지 않아 대충만 정리하도록 하겠다. 우선, 컴퓨터로 한글인 문제들을 훑었다. E가 쉬워보였고, 가장 먼저 풀이를 찾은 qjatn0120 선배가 짜서 맞았다. 이후 문제지가 도착해 slah007 선배는 A, qjatn0120 선배는 C, 나는 K를 잡았다, A와 C는 무난히 맞았지만, K는 다익스트라가 돌 것이라 생각한 나의 오판으로 TLE를 몇 번 받았다. 이후 DAG임을 깨닫고 DP를 짰지만, 이 역시 TLE를 받았다. 결국 G를 풀고 온 qjatn0120 선배가 받아서 AC. F 역시 slah007 선배가 TLE를 계속 받아 qjatn0120 선배가 새로 짜 AC를 받았다. 이후 1시간 가량 나와 qjatn0120 선배는 J, sl..

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) 대충 해보면, 우물 정..

공휴일에 좋은 대회가 있길래 팀 연습을 했다. 내가 뒤, slah007 선배가 앞, qjatn0120 선배가 가운데를 보고 시작했다. 세팅 문제 때문에 5분쯤 늦게 시작했다. ~0:32 slah007 선배는 D, 나는 J, qjatn0120 선배는 H를 봤다. 가장 먼저 코딩에 들어간 H를 27분에 AC받고, 쉬운 문제였던 D 역시 32분에 AC가 나왔다. 나는 J를 보다 어려워서 던진 후 많이 풀린 B로 넘어갔다. ~1:08 B에서 끙끙대다 qjatn0120 선배가 핵심적인 관찰을 해 주셔서 바로 코딩에 들어갔다. 무지성으로 세그를 짠 뒤 mod 이슈로 한 번 틀린 후 B를 맞았다. ~2:27 이후 A, J, E의 코딩이 번갈아서 진행되었다. J는 사풀인걸 알지만 코딩이 짧아 qjatn0120 선배가 ..

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

3인 5시간 셋을 2인 3시간으로 쳤다. 셋은 BAPC 2019를 사용하였다. 내가 뒤, slah007 선배가 앞을 보고 시작했다. ~0:07 브론즈 문제인 J와 B를 풀었다. J는 안쓰던 컴이라 괜히 int 썼다가 오버플로우로 한 번 틀렸다. ~0:30 H AC를 받았다. \(10^8\)짜리 풀이인데 63ms에 돌아서 신기했다. ~0:50 slah007 선배가 오래 잡고 있던 E를 맞았다. 약간 귀찮은 DP인 것 같았다. ~0:55 slah007 선배의 E와 번갈아 내가 코딩을 하던 A를 맞았다. ~1:08 그리고 F를 봤는데 많이 본 유형이라 그냥 슥슥 풀었다. slah007 선배는 귀찮은 구현 문제인 G를 잡았다. ~1:57 slah007 선배가 G를 맞았다. 나는 I, K, L를 잡고 있었는데, ..