ABC336 E - Digit Sum Divisible

Competitive Programming C++

2024-01-15

공식 에디토리얼

문제 링크
https://atcoder.jp/contests/abc336/tasks/abc336_e

원문 링크
https://atcoder.jp/contests/abc336/editorial/9055

이 문제는 숫자의 자릿수에 대한 조건을 만족하는 정수의 개수를 세는 문제입니다.
이런 유형의 문제는 Digit DP 라는 종류의 DP가 효과적인 경우가 많고, 실제로 이 문제도 Digit DP를 이용하면 빨리 풀 수 있습니다.

이 문제는 처음에는 자릿수의 합 \(s\)를 고정하고 생각하는 것이 포인트입니다.
즉, \(s = 1, 2, …, 9 \times 14\)라고 고정한 상태에서 문제를 풀고, 모든 \(s\)에 대한 답을 합친 것이 전체의 답이 됩니다.

\(s\)를 고정하고 생각했을 때, DP 상태를 다음과 같이 나타낼 수 있습니다.

\[dp_{d,i,j,f}=(위에서부터\ d자리까지를\ 정했을\ 때,\ 자릿수의\ 합이\ i고,\mod s가\ j고,\ f = 0이면\ N 미만,\ f = 1이면\ N과\ 일치하는\ 정수의\ 개수)\]

위와 같이 두고 Digit Dp를 하면 \(d + 1\)자리째를 \(t\)라 두었을 때

\[dp[d + 1][i + t][(10j + t)\mod s][대소관계의\ 정보] \mathrel{+}= dp[d][i][j][k]\]

와 같이 DP 점화식을 가지고 답을 계산할 수 있습니다.

계산량은 \(B = 10\)으로 뒀을 때 전체 \(O((B\log N)^4)\)입니다.
(여기서 \(\log N\)은 \(N\)의 자리수의 의미이므로, 밑은 10인 상용로그이며, \((B\log_{10} N)^4 \leq (140)^4 \simeq 3.8 \times 10^8\)입니다. 일반적인 문제보다 크지만, 시간 제한이 10초로 넉넉하게 설정되어 있기 때문에, 적당히 구현하면 시간 내에 돌게 할 정도로 빠르게 동작합니다.)

Digit DP는 좀…

보자마자 자릿수로 DP 해야 한다는 것까진 알았지만, D까지 너무 늦게 풀어서 심적인 여유가 없었고 점화식도 잘 안 세워져서 이번에도 ABCD만 푸는 것에 그쳤다.

F도 만만찮았는데… 이번은 날이 아니었나보다.