Clockwise

Hello 2024 라운드를 대비하기 위해 버츄얼을 돌았다. FD..LH..lloyJ(김도훈이라고 읽는다고 한다..)와 sharaelong님이랑 같이 돌았다. 특이사항으로는 E, F가 모두 난이도 있는 트리 문제였는데, 두 문제 다 예전에 풀어본 문제들 중 하나랑 비슷한 점이 있었는데도 불구하고 대회 시간 내에 해결하지 못했다. 다만 D와 E의 난이도 차이가 커서 그런지 퍼포먼스는 2432가 나왔다. https://codeforces.com/contest/1905 A. Forked! [00:09:46, -1] *900 관점을 바꿔서 생각한다. 두 왕이 이동할 수 있는 칸 중, 몇 개의 칸이 겹치는지 세면 쉽다. https://codeforces.com/contest/1904/submission/24024..

지난번에 있었던 코포 라운드에서 뜻하지 않게 탑레를 갱신하게 되었다. 다운보트를 무려 4000개나 받은 역대급 셋이었지만 내가 많이 올랐으면 된 게 아닐까..? 아무튼 레드가 갑자기 가시권으로 다가오게 돼서 버츄얼을 시간 날 때마다 돌기로 했다. kongum과 leo020630과 함께 돌았다. 문제 셋 퀄리티는 좋았고, 난이도 밸런스도 적당했다. 아쉬웠던 점은 1시간 정도 남기고 E, F를 둘다 못 풀었다는 점인데, 둘 다 그렇게 어려운 문제가 아니었어서 조금 아쉽게 느껴진다. 예상 퍼포먼스는 2305가 나왔다. https://codeforces.com/contest/1905 A. Constructive Problem [00:02:01] *800 초기 배치하는 칸을 대각선으로 이어지게 잘 배치해주면 된다..

레드가 가고 싶다던 Jeuti와 버츄얼을 돌았다. 그리고 같이 망했다. https://codeforces.com/contest/1887 A1. Dances (Easy version) [00:07:42] *1400 Easy version 에서는 한 번만 비교해 주면 된다. 최적의 결과는 $A$와 $B$ 배열을 각각 정렬한 뒤, $A$의 Prefix와 $B$의 Suffix를 순서대로 매칭시켜 봄으로써 얻을 수 있다. 이제 답에 대한 이분 탐색을 하면 $O(NlogN)$에 풀 수 있다. https://codeforces.com/contest/1887/submission/239066721 A2. Dances (Hard version) [00:50:19, -1] *1900 Hard version 에서는 $M$번이..

https://atcoder.jp/contests/abc254/tasks/abc254_h kenkoooo 레이팅: 2499 체감 난이도: P1 Tag: Greedy, Bitmask $N$개의 수로 이루어진 두 multiset $A, B$가 주어진다. 다음 연산을 최소 횟수로 사용해서 $A$를 $B$와 같게 만들 수 있는지 구해야 하는 문제이다. $A$에 있는 원소 $n$을 고른다. 그 원소를 지우고, $A$에 $2n$을 추가한다. $A$에 있는 원소 $n$을 고른다. 그 원소를 지우고, $A$에 $\lfloor \frac{n}{2} \rfloor$를 추가한다. 본 대회 때는 풀지 못했던 문제이다. 접근의 큰 틀은 맞았으나, 세부적인 구현이 많이 꼬여 있었다. 다시 풀어보는데도 디버깅에 한 세월 쓴 거 봐..

https://atcoder.jp/contests/abc221/tasks/abc221_h kenkoooo 레이팅: 2793 체감 난이도: D5 Tag: DP, Combinatorics 두 수 $N, M$이 주어진다. $1$ 이상 $N$ 이하의 모든 정수 $k$에 대해, 아래 조건을 만족하는 집합의 수를 $998\ 244\ 353$로 나눈 나머지를 구해야 한다. 집합에 있는 원소의 수는 $k$이다. 모든 원소의 합은 $N$이다. 같은 원소는 최대 $M$개까지 포함할 수 있다. 집합은 순서를 구분하지 않기 때문에 막 세는 것이 조금 까다롭다. 핵심은 구하고자 하는 것을 잘 변형해서 세기 쉬운 형태로 잘 바꿔주는 것이다. 풀이에서는 순서를 구분해서 세도 되는 형태로 조건을 잘 변형한다. $A$는 항상 오름차순..

https://atcoder.jp/contests/abc259/tasks/abc259_h kenkoooo 레이팅: 2881 체감 난이도: D3 (근데 이 정도 난이도의 수학 문제는 풀어본 적이 없어서 잘 모르겠다.) Tag: Math, Bitmask $N$ 종류의 카드가 있다. $i$번 종류의 카드는 $A_i$가 쓰여 있고, 총 $B_i$장이 있다. $M$개의 카드를 고른 뒤, 그 카드에 있는 수를 모두 곱한 값을 $S$라고 하자. 카드를 고르는 모든 경우에서의 $S$ 합을 $998\ 244\ 353$으로 나눈 나머지를 출력하는 문제이다. $N$이 $16$ 정도로 작다는 점을 유념하자. 에디토리얼의 도움을 받았다. 아래 내용은 수학적으로 아마 엄밀하지는 않을 거고, 이해한 풀이의 흐름을 기반으로 서술되어..

https://atcoder.jp/contests/abc259/tasks/abc259_h kenkoooo 레이팅: 2406 체감 난이도: P1 Tag: DP, Sqrt Decomposition $N \times N$ 크기의 격자 위에 수 $A_{i, j}$가 쓰여있다. 어떤 칸에서 인접한 오른쪽 칸이나 아래쪽 칸으로 이동할 수 있다. 모든 경로 중, 경로의 시작점과 끝점에 있는 수가 같은 경로의 수를 구해야 하는 문제이다. 각 수마다 독립적으로 문제를 해결하려고 시도해보자. 각 수의 등장 횟수를 $S_i$라고 표기한다. (i) $S_i$가 작으면, $O(S_i ^ 2)$ DP를 이용해 문제를 해결할 수 있다. (ii) $S_i$가 크면, $O(N^2)$ DP를 이용해 문제를 해결할 수 있다. 두 방법을 ..

비정기적으로 ABC의 Ex 난이도에 해당하는 문제를 하나씩 풀고 포스팅해 볼 것이다. 고난이도 문제에서 교육적인 컨셉이나 개념을 얻어가서 공부 좀 해보자는데 의의를 두려고 한다. https://atcoder.jp/contests/abc267/tasks/abc267_h kenkoooo 레이팅: 2422 (오렌지지만, Ex 중에서는 가장 쉬운 편에 속하는 문제이다.) 체감 난이도: D5 ~ D4 Tag: FFT, Divide and Conquer $N$개의 원소로 이루어진 수열 $A$가 주어진다. 이 수열에서 홀수 개의 원소를 골라, 그 합이 $M$이 되게 하는 경우의 수를 구하는 문제이다. $N$이 $100\ 000$으로 작지 않지만, $A$가 $10$밖에 되지 않는다는 점이 특이하다. 다항식을 이용해서 ..

https://codeforces.com/contest/1737 A. Treasure Chest [00:03:35] 열쇠의 위치가 상자보다 왼쪽에 있다면 상자를 굳이 옮길 필요가 없다. 상자가 열쇠보다 왼쪽에 있다면 가능한 상자를 오른쪽으로 옮겨줘야 한다. 열쇠 위치에 도달했다가 다시 상자로 와야 하기 때문이다. https://codeforces.com/contest/1895/submission/231136403 B. Points and Minimum Distance [00:06:58] $x$와 $y$ 를 분리해서 생각해도 상관이 없고, $A$를 정렬하고 시작하자. 1차원인 경우에는 단순히 $A_{2N} - A_1$이 답이 되는데, 따라서 2차원인 경우에도 비슷하게 $A_{2N} - A_{N+1} + A..

https://codeforces.com/contest/1737 A. Ela Sorting Books [00:06:39] A 치고 지문이 너무 긴게 마음에 들지 않는다. 사전순 최대를 뽑아야 하므로, a b c... 순으로 가능한만큼 뽑아주면 된다. 남는 문자들을 그냥 적당히 분배한다고 생각하면 정당성을 약간 보태줄 수 있다. https://codeforces.com/contest/1737/submission/174983929 B. Ela's Fitness and the Luxury Number [00:16:02] [L, R] 구간에서 특정 조건을 만족하는 수들을 구하는 문제는, [1, n] 구간에서 조건을 만족하는 수들을 찾는 문제로 변환해서 해결하는 것이 기본이다. 문제의 조건을 만족하는 수들의 특징..