leo020630의 블로그

시험도 끝났겠다 앳코더 계정을 옐로로 올려놓기 위해 ABC를 쳤다. A. Zero Sum Game (0:01, +) * 제목에 풀이가 써 있다. Zero Sum Game이므로 -(주어지는 수의 합)을 출력하자. B. Commencement (0:03, +) * 시키는 대로 구현해주면 된다. C. Airport Code (0:09, +2) * 앞에서부터 \(T\)의 각 문자가 등장할 때마다 그리디하게 골라주면 된다. 코딩을 절어서 2번 틀렸다. D. Divide Interval (0:15, +) * 정확한 증명은 모르겠지만 왠지 그래야 할 것 같은 코드를 짜서 맞았다. 갈 수 있는 한 최대로 계속 가주면 된다. E. Weighted Tic-Tac-Toe (0:27, +1) * 일단 게임이고, 제한을 보면 ..

여러 이슈로 1달만에 치는 코포다. A. Did We Get Everything Covered? (0:09, +) 딥1 A인만큼 막 쉽지는 않았다. 하지만 뭔가 어떻게 해야 한다는 직감이 빠르게 들어서 그대로 짰다. 각 문자가 1개씩 등장할 때까지 뽑는 것을 반복하면 된다. 역추적을 대충 생각했다가 예제가 나오지 않아 고쳐서 맞았다. 역추적은 각 차례에서 가장 늦게 등장한 알파벳을 저장해주면 된다. B. Space Harbour (0:34, +) B번에서는 코포답지 않게 국밥 냄새가 강하게 났다. 최대한 빨리 풀어야한다는 마음가짐으로 문제를 읽었다. 읽어보니 업데이트는 대충 셋에서 양쪽을 보면 되고, 구간을 일차함수로 초기화하는 레이지 세그가 있으면 될 것 같았다. 조금 생각해보니 잘 짜면 될 것 같아서..

블로그에 처음 쓰는 아레나 후기 글이다. 아레나 #1은 계절학교와 병행해서 + C를 그냥 못 풀어서 등수를 박았고, 아레나 #2는 할 만큼 했으나 페널티로 인해 낮은 퍼포를 받았다. 두 대회 모두 딱히 복기할 거리도 없었다. 아레나 #3인 MatKor Cup은 깡수학 대회라길래 걸렀고, 아레나 #4 KSA 대회는 검수진이었다. 이러한 상황에서 아레나 #5인 SUAPC는 잘 칠 필요가 있었기 때문에 조금 집중해서 대회를 쳤다. SUAPC는 지난 2번의 대회에 출제진으로 참여한 적도 있었던 만큼, 기대를 안고 대회를 쳤다. ~0:12 대회를 켰는데, 일단 문제 수가 많았다. 내가 알기로 SUAPC는 13문제 체제로 유지되었던 것 같은데, 14문제가 나를 반기고 있었다. 같은 상황을 겪은 PPC와 대충 비슷한..

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) 연산으로 바꿀 수 있는 수가 없는 경우나 모든 수가 같은 경우는 예외처리..

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 대충 어떻게 하면 될 지는 보이는데, 구현이 귀찮다. 앞부터 그리디하게 처리해주면 된다. 개수는 뒤 동..

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\)의 배수들끼리 정렬해준 후 전체 배열..