leo020630의 블로그

Div. 1이 있어 오랜만에 코포를 쳤다. A. Increasing and Decreasing (0:02, +) 공차를 뒤에서부터 1, 2, .. 로 설정해준 후 마지막에 수를 몰아서 쓰면 된다. B. Swap and Reverse (0:05, +) \(k\)가 짝수이면 문자열을 자유롭게 변형할 수 있고, 홀수이면 인덱스의 홀짝성을 유지한 채 자유롭게 바꿀 수 있다. 따라서 경우를 나눈 후 문자열을 정렬해주면 된다. C. Divisor Chain (0:44, +2) 쉽게 생각할 수 있는 방법이 다 반례가 있는 것 같아 뇌정지가 왔다. 이상한 풀이로 페널티를 적립하던 중 괜찮은 접근이 떠올라 증명 없이 내서 맞았다. 2의 거듭제곱에 한 번 도달하면 쉽게 끝을 낼 수 있는데, 여기 도달하기 위해 현재의 수를..

오랜만에 코포를 쳤다. A1. Dual (Easy Version) (0:14, +) A가 1/2로 나뉘어 있길래 1부터 풀었다. 횟수가 넉넉해서 대충 하나를 좀 키우고 2배씩 커지도록 만들면 될 것 같았다. 그대로 짜서 AC를 받았다. A2. Dual (Hard Version) (0:50, +2) 2는 1의 접근법을 사용할 수 없었다. 우선 한 가지 관찰이 필요하다: 모든 수가 0 이상이거나 모든 수가 0 이하이면 \(N-1\)번의 연산으로 단조 수열을 만들 수 있다. \(N=20\)이므로 우리는 12번 안에 모든 수를 0 이상 혹은 이하로 만들어야 한다. 이제 주어진 수열에서의 양수의 개수를 \(a\), 음수의 개수를 \(b\), 양수 중 최댓값을 \(x\), 음수의 절댓값 중 최댓값을 \(y\)라 하..

밀린 후기가 있어 이것만 작성하고 UCPC 후기를 쓰려 한다. Div. 4에서 1등을 했더니 3은 칠 기회도 없이 Div. 2로 와버렸다. P1. Card Swipe (0:02) 잘 구현해주면 된다. P2. Exclusion-Inclusion (0:04) 작은 값부터 빼주면 된다. P3. Segment Three (0:19) 각 원소 당 더해야 하는 숫자는 최대 2이다. 저 쉬운 풀이가 있을 것 같기도 한데 잘 모르겠어서 \(O(27N)\) 3진법 Bit DP를 돌렸다. P4. Two Piles (0:32) 어디서 많이 본 문제라 바로 짰다. 대충 하나 고정하고 스위핑을 잘 해주면 된다. P5. Maximize Ones (0:54) 연산으로 바꿀 수 있는 수가 없는 경우나 모든 수가 같은 경우는 예외처리..

적당한 시간대에 오픈컨이 있길래 가서 쳤다. 처음엔 사람들 닉네임이 무서워서 쫄았는데, 문제들이 어렵지 않아서 결과가 나름 괜찮게 나왔다. 따라서 후기를 써 보려 한다. 카테고리는 적절한 곳이 없어서 거의 1년 만에 오늘의 PS를 부활시켰다. 다음 글이 언제가 될진 잘 모르겠다.. 셋: https://www.acmicpc.net/category/detail/3626 A. 10! (0:01, +) *B4 구현해주면 된다. 0분대 솔브도 가능했을 것 같은데 똑똑한 방법을 찾지 못하고 계산기로 10!/6을 계산하느라 조금 늦었다. B. 고양이 카페 (0:06, +1) *S3 비슷한 문제를 굉장히 많이 봐서 바로 짰다. 제일 작은 원소부터 가능한 원소와 매칭시켜 주면 된다. upper를 lower로 잘못 써서 ..

menborong님이 CodeChef가 괜찮다고 추천을 꾸준히 하셨는데, 학기 중에는 시간이 없어서 못 치고 이제야 첫 라운드에 도전했다. CodeChef 라운드는 큰 문제 셋을 적당히 쪼개서 Division 1~4로 나누어 운영되는 것 같다. 나는 첫 참가였기에 Div. 4에 배정되었다. menborong과 qjatn0120 선배가 본인들은 1등 했다고 주장하셔서 1등을 목표로 임했다. 제출에 의한 페널티가 없다고 해 제출은 막 했다. P1. Messi vs Ronaldo (0:01) *316 브론즈 5 문제이다. 그냥 짜면 된다. P2. FIND A and B (0:03) *802 각 수를 B에 대입하고 다른 두 수로 A를 만든 후 판별해주면 된다. P3. Airport Management (0:14..

지난 Div.1의 여파 이후 이틀을 쉬고 버츄얼을 다시 돌았다. A. AB Balance (0:07, +) *900 A치고 좀 어려웠던 것 같다. 뭔가 복잡한 풀이가 떠올랐는데, 아닌 것 같아서 좀더 생각해 보니 첫 글자와 마지막 글자가 같기만 하면 된다는 사실을 알 수 있었다. B. Update Files (0:13, +1) *1100 현재 파일 수가 \(k\)보다 적으면 계속 2배가 되고, 아니라면 \(k\)씩 더해진다. 앞은 반복문으로 대충 처리하고, 뒤는 나눗셈으로 횟수를 구해주면 된다. 그냥 무지성 반복문을 썼다가 TLE를 한 번 받아버렸다. C. Banknotes (0:25, +) *1400 대충 어떻게 하면 될 지는 보이는데, 구현이 귀찮다. 앞부터 그리디하게 처리해주면 된다. 개수는 뒤 동..

주말에 앳코더 2개, 코포 2개를 쳤는데 언레는 대충 치고 레이티드는 이상한 짓 해서 말았습니다. 몸 컨디션이 별로였는데 결국 퍼포에 영향을 미치네요.. 이상한 요소로 억까당하니 마음이 꺾였습니다. 다음 라운드부터 다시 열심히 정리해보도록 하겠습니다ㅜ

Div. 1을 돌자는 menborong님의 의견이 있어서 Div. 1을 돌았다. 어차피 C까지는 Div. 2에도 다 있어서 상관 없었던 것 같다. A. Array Elimination (0:03, +) \(k\)는 비트별로 봤을 때 1의 개수의 공통 약수여야 한다. gcd를 구해 주면 된다. 모두 0일때만 조심하자. B. Frog Traveler (0:52, +3) 이 테크닉을 박으면 풀리는 형태라 박았다. 루트 버전으로 짜고 MLE를 3번 받은 후에야 세그트리 모양으로 갈아타서 맞았다. 정해가 쉬운데 조금 더 생각을 하는게 옳은 방향이었던 것 같다. C. Optimal Insertion (1:48, +2) B의 원소들을 넣어야 하는 최적의 위치를 찾아주자. B의 원소를 오름차순으로 보면서, 각 위치에 ..

:god: tlsdydaud1님이 세팅하신 라운드이다. 역시 버츄얼로 돌았다. A. Distance and Axis (0:03, +) \(A\)의 위치는 \(x = 2y+k\)꼴이 되어야 한다. \(n\)이 \(k\) 미만이면 \(k\)까지 옮기고, 아니면 최대 1칸 이동해 조건을 만족시킬 수 있다. B. Ternary Sequence (0:10, +) 비용이 2-1인 경우와 1-2인 경우가 아니라면 다 0이라는 것을 알 수 있다. 따라서 2를 최대한 써주고 -2를 최소한으로 쓰면 된다. C. Mere Array (0:15, +) 최솟값을 \(m\)이라 하자. \(gcd(m,mk)=m\) 이므로 \(m\)의 배수들끼리는 위치를 자유롭게 바꿀 수 있다. 따라서 \(m\)의 배수들끼리 정렬해준 후 전체 배열..

방학 기간에 동아리 부원들과 1일 1버츄얼을 돌리기로 했다. A. Replacing Elements (0:02, +) 정렬을 한 후, \(d\)보다 큰 수는 \(a_1 + a_2\)로 바꿔주어야 한다. B. String LCM (0:06, +) 길이를 \(|s||t|\)까지만 확인해보면 된다. 그냥 짜주자. C. No More Inversions (0:30, +1) 그냥 밑바닥에서 규칙을 찾아야 하는 코포식 문제다. 뭔가 해보다 보면 대칭인 부분을 잘 뒤집어주면 된다는 사실을 알 수 있다. 자세한 증명은 에디토리얼에 있다. D. Program (0:42, +) 더하는 수가 +-1로 연속적이므로 누적합의 최댓값과 최솟값을 구하면 된다. 앞에서부터의 최대, 최솟값과 뒤에서부터의 최대, 최솟값을 저장하면 해결..