leo020630의 블로그

방학 기간에 동아리 부원들과 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로 연속적이므로 누적합의 최댓값과 최솟값을 구하면 된다. 앞에서부터의 최대, 최솟값과 뒤에서부터의 최대, 최솟값을 저장하면 해결..

A. Game with Board (0:06, +1) $n$이 5 이상이면 Alice가 1을 두 개만 남기고 줄 수 있다. 그렇지 않은 경우에는 Bob이 항상 이긴다. 대충 생각했다 한 번 틀렸다. B. Keep it Beautiful (0:11, +) 정렬된 상태인지 검사하고, 만약 깨진다면 그 뒤가 여전히 정렬된 상태이면서 첫 번째 수보다 작은지 계속 검사해주면 된다. C. Ranom Numbers (0:32, +) C치고 굉장히 어려웠다. 뭔가 그리디적인 방법을 시도해보고 싶지만, 그러다간 말리기 쉽다. 숫자 종류가 5개로 작으므로 모든 경우를 다 시도해보자. 우선 주어진 문자열에 대한 답을 계산한 후, 문자를 하나씩 바꿔볼 것이다. 문자를 바꾸면 이전에 위치한 문자들의 부호가 달라질 수 있는데, ..

처음 오렌지를 찍고 1년 2개월이 지난 후, 드디어 International Master(찐렌지)에 도달했습니다. 하지만 이 과정이 일반적이지 않고 너무나도 기묘했기 때문에 글으로 기록해보려 합니다. 찐렌지에 도달한 라운드는 한국 시간 기준 화요일 밤에 있었는데, 토~화 4일동안 친 코드포스 3개와 앳코더 2개 라운드에 대한 후기와 전체적인 소감을 다룰 예정입니다. 카테고리는 애매했는데 그냥 CP로 두기로 했습니다. 2/25 (토) 21:00 - AtCoder Regular Contest 157 A. XXYYX (0:10, +4) *348 생각을 대충 하고 넘어갔더니 A번에서 4번 틀리고 10분이 걸렸습니다. 문제 자체는 쉽습니다. B. XYYYX (1:06, +8) *1529 라운드를 망친 원흉입니다...

A. Two Towers (0:02, +) B를 뒤집어서 합친 후 끊는 것으로 생각할 수 있다. RR이나 BB가 최대 1번 등장하면 YES, 아니면 NO이다. B. Ideal Point (0:06, +) 옆 두 점과 비교해 더 많기 위해서는 결국 [x, x] 형태가 존재하거나 [~,x], [x,~]가 하나씩 존재해야 한다. 이를 체크해주면 된다. A와 B 모두 \(O(N)\)에 풀 수 있으나 발상이 어려워서인지 제한이 작았다. C. Tea Testing (0:13, +) B에 대한 누적합 배열을 만들고, 각 차에 대해 이분탐색을 해주면 각 차를 온전히 먹는 사람과 일부만 먹는 사람을 구할 수 있다. 온전히 먹는 사람은 구간으로 나타나는데, imos법을 이용해 마지막에 처리해준 후 답을 구하면 깔끔하게 구..

어제 갑자기 블로그 조회수가 튀었길래 원인을 확인해보았더니 모 PS 커뮤니티에서 의문의 PS러가 이 블로그를 일종의 우수 블로그로 선정해주었다는 사실을 알게 되었다. 엄청난 분들과 함께 이름이 올라가 있어 기분이 좋았다. 뽑힌 김에 블로그 활동을 조금 더 성실히 해 보고자 오늘 있던 코포 후기부터 작성해보려 한다. A. Flip Flop Sum (0:02, +) 원래 합을 \(S\)라 하자. 모두 1이면 \(S-4\), 연달아 있는 -1이 하나라도 있으면 \(S+4\), 모두 아니면 \(S\)가 답이다. B. The Forbidden Permutation (0:14, +1) 문제가 좀 억지스럽다. 일단 Not good인지 판별을 먼저 하고, Not good이라면 인접한 쌍을 역전시키거나 거리를 \(d\)..

A. Indirect Sort (0:01, +) \(A_1\)이 1이어야 한다. B. Maximum Substring (0:05, +) 어떤 부분문자열에 두 문자가 하나 이상 있으면 그냥 쭉 늘려주는 것이 최적이다. 따라서 전체 문자열의 값과 같은 문자가 연속으로 가장 길게 있는 경우만 비교해주면 된다. C. Complementary XOR (0:20, +) 모든 숫자가 0인 경우부터 거꾸로 생각해보자. 이 상태에서 연산을 한 번 적용하면 A와 B의 모든 원소가 다른 값이 되고, 한번 더 적용하면 다시 A와 B의 모든 원소가 같아진다. 따라서 가능한 경우는 A와 B가 모두 같거나 모두 다른 경우이다. 해를 찾는 방법은 A를 우선 모두 1로 만들자. 이러면 B가 모두 0이거나 모두 1인데, 모두 0이면 1..

A. Factorise N+M (0:00, +) 홀수면 3, 짝수면 2를 출력하면 된다. B. Jumbo Extra Cheese 2 (0:05, +) 둘 중 작은 쪽을 가로로 쓰는게 항상 이득이고, 세로는 정렬한 모양으로 쓰는 것이 이득이다. 증명은 잘 모르겠다. C. Bricks and Bags (0:16, +) 한쪽 끝에 2개빼고 다 넣고, 남은 2개에 하나씩 넣는게 최적이다. 역시 증명은 잘 모르겠다. 이름이 헷갈려서 해석이 오래 걸렸다. 그냥 Alice Bob 쓰면 될 것을.. D. Knowledge Cards (0:40, +1) 새 카드를 꺼낸 후 보드에 빈 자리가 하나라도 있으면 잘 옮겨줄 수 있다. 구현을 이상하게 해서 1번 틀렸다. E. Hanging Hearts (1:02,+1) 잘 생각..

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, 한쪽 끝이 막혀있는 경우 칸 수, 두 끝이 막혀있는 경우 칸 수의 홀짝성이 그런디 수가 된다. 그대로 스프라그 그런디 정리를 적용해주면 된다...

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