📝 문제 정보#
🧐 관찰 및 접근#
- 안에서부터 각 동심원에 대해 다음과 같은 DP식을 생각해보자.
- $\text{DP}[i][j]$: $i$번째 동심원까지 그렸을 때 $j$통의 빨강 페인트를 쓰는 경우의 수
- 그러면 파란 페인트는 $\sum\limits_{k = 1}^i k - j$ 통 필요하다.
- 이게 $b$이하면 여유롭게 된다!
- 그러면 파란 페인트는 $\sum\limits_{k = 1}^i k - j$ 통 필요하다.
- 시간복잡도는.. $a+b \leq 100000$이므로 500번 안쪽으로 끝날거고, 그에 맞춰 나이브하게 구하면 업데이트에 5만번, 합을 구하는데 5만번이니… 500 * 50000 = 25'000'000번?
- 근데 테케가 10000개라는 이슈가 있다… 이걸 더 줄여야만 해
- $\text{DP}[i][j]$: $i$번째 동심원까지 그렸을 때 $j$통의 빨강 페인트를 쓰는 경우의 수
- 아하, 다시 보니까 DP식은 안바뀐다.
- 그러면 그냥 $500 * 50000$ 테이블을 만들어놓고, 누적합을 이용해서 한번에 구하자.
💻 풀이#
- 코드 (C++):
void solve(){
vector<vector<mint>> DP(501, vector<mint>(50001, 0)), pfSum(501, vector<mint>(50002, 0));
DP[0][0] = 1;
rep(i, 1, 501) rep(j, 0, 50001) DP[i][j] = DP[i-1][j] + (j >= i ? DP[i-1][j-i] : 0);
rep(i, 0, 501) rep(j, 0, 50001) pfSum[i][j+1] = pfSum[i][j] + DP[i][j];
int tc; cin >> tc;
while(tc--){
ll a, b; cin >> a >> b;
ll sum = 0;
mint ans = 0;
rep(i, 1, 501){
sum += i;
if(sum > a + b) break;
ans += pfSum[i][min(a, sum) + 1] - pfSum[i][max(0LL, sum - b)];
}
cout << ans << '\n';
}
}