AtCoder 5

[ABC254 Ex] Multiply or Divide by 2

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$를 추가한다. 본 대회 때는 풀지 못했던 문제이다. 접근의 큰 틀은 맞았으나, 세부적인 구현이 많이 꼬여 있었다. 다시 풀어보는데도 디버깅에 한 세월 쓴 거 봐..

AtCoder 2023.11.19

[ABC221 H] Count Multiset

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$는 항상 오름차순..

AtCoder 2023.11.16

[ABC241 Ex] Card Deck Score

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$ 정도로 작다는 점을 유념하자. 에디토리얼의 도움을 받았다. 아래 내용은 수학적으로 아마 엄밀하지는 않을 거고, 이해한 풀이의 흐름을 기반으로 서술되어..

AtCoder 2023.11.14

[ABC259 Ex] Yet Another Path Counting

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를 이용해 문제를 해결할 수 있다. 두 방법을 ..

AtCoder 2023.11.12

[ABC267 Ex] Odd Sum

비정기적으로 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$밖에 되지 않는다는 점이 특이하다. 다항식을 이용해서 ..

AtCoder 2023.11.12