PrefixSum

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/22348 🧐 관찰 및 접근 # 안에서부터 각 동심원에 대해 다음과 같은 DP식을 생각해보자. $\text{DP}[i][j]$: $i$번째 동심원까지 그렸을 때 $j$통의 빨강 페인트를 쓰는 경우의 수 그러면 파란 페인트는 $\sum\limits_{k = 1}^i k - j$ 통 필요하다. 이게 $b$이하면 여유롭게 된다! 시간복잡도는.. $a+b \leq 100000$이므로 500번 안쪽으로 끝날거고, 그에 맞춰 나이브하게 구하면 업데이트에 5만번, 합을 구하는데 5만번이니… 500 * 50000 = 25'000'000번? 근데 테케가 10000개라는 이슈가 있다… 이걸 더 줄여야만 해 아하, 다시 보니까 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'; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/11066 🧐 관찰 및 접근 # 파일 $C_i, C_{i+1}, \cdots, C_{j}$를 합치고 싶다고 하자. 이때, 해당 값은 $\text{DP}[i][j] = min_{i \leq k < j}(\text{DP}[i][k] + \text{DP}[k+1][j])$이 성립한다. 이는 $O(N^3)$이므로 충분히 돈다. 이런 문제는 top-down 재귀 DP로 구현하면 조금 더 편하게 짤 수 있다. TMI) 크누스 최적화를 이용해 더 빠르게도 풀 수 있다! 💻 풀이 # 코드 (C++): ll calc(int L, int R){ if(L == R) return 0; ll &ret = DP[L][R]; if(ret != -1) return ret; ret = LLONG_MAX; rep(k, L, R) ret = min(ret, calc(L, k) + calc(k+1, R) + (pfsum[R] - pfsum[L-1])); return ret; } void solve(){ cin >> N; rep(i, 1, N+1) cin >> C[i]; rep(i, 1, N+1) pfsum[i] = pfsum[i-1] + C[i]; rep(i, 1, N+1) rep(j, 1, N+1) DP[i][j] = -1; cout << calc(1, N) << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/18830 🧐 관찰 및 접근 # 11차원인게 조금 이슈이므로, 간단하게 3차원정도로 생각해보자. 2차원이면 그냥 누적합 배열에서 $S(a_2, b_2) - S(a_1, b_2) - S(a_2, b_1) + S(a_1, b_1)$이었던 것이 기억난다. $a_1, b_1, c_1, a_2, b_2, c_2$가 주어진다. $a_1 \leq \alpha \leq a_2, b_1 \leq \beta \leq b_2, c_1 \leq \gamma \leq c_2$ 인 어쩌구에 대해 합을 출력한다. 이를 누적합으로 생각하면, $S(a_2, b_2, c_2) - S(a_1, b_2, c_2) - S(a_2, b_1, c_2) - S(a_2, b_2, c_1) + S(a_1, b_1, c_2) + S(a_1, b_2, c_1) + S(a_2, b_1, c_1) - S(a_1, b_1, c_1)$ 인 것 같다! 아님말고 암튼 $n$차원일때 누적합 배열을 구해둔다면 $2^n$의 시간복잡도로 계산할 수 있는 것 같다. 쿼리가 4만개이므로 $40000 * 2048 = 81920000$이므로 충분히 돌 것 같다. 그런데 누적합 배열을 만드는게 $O(2^n * mno...w)$ 라서 이게 20억인데… 포함배제로 구하지 말고, 차원에 대해서 구하고 밀어버리자. 💻 풀이 # 코드 (C++): const int cdim = 11; using v11 = array<int, cdim>; v11 dim, sz; int totSz; vector<ll> A, pfsum; int point_to_idx(const v11 &point){ int idx = 0; rep(d, 0, cdim) idx += point[d] * sz[d]; return idx; } vector<ll> make_prefix_sum(int cd = 0, v11 cp = {}){ vector<ll> res; if(cd == cdim){ int idx = point_to_idx(cp); res.push_back(A[idx]); return res; } rep(i, 0, dim[cd]){ cp[cd] = i; vector<ll> tmp = make_prefix_sum(cd+1, cp); if(res.empty()) res = tmp; else{ rep(j, 0, tmp.size()) res.push_back(res[(i-1) * sz[cd] + j] + tmp[j]); } } cp[cd] = 0; return res; } void solve(){ rep(i, 0, cdim) cin >> dim[i]; sz[cdim-1] = 1; rrep(d, cdim-1, 0) sz[d] = sz[d+1] * dim[d+1]; totSz = sz[0] * dim[0]; A.resize(totSz); pfsum.resize(totSz, 0); rep(i, 0, totSz) cin >> A[i]; pfsum = make_prefix_sum(); int Q; cin >> Q; while(Q--){ v11 L, R; rep(d, 0, cdim) cin >> L[d]; rep(d, 0, cdim) cin >> R[d]; rep(d, 0, cdim) L[d]--, R[d]--; ll ans = 0; rep(mask, 0, (1<<cdim)){ v11 point = R; bool add = true, flag = true; rep(d, 0, cdim) if(mask & (1<<d)){ point[d] = L[d]-1; add = !add; if(point[d] < 0){ flag = false; break; } } if(!flag) continue; int idx = point_to_idx(point); if(add) ans += pfsum[idx]; else ans -= pfsum[idx]; } cout << ans << "\n"; } } 🔒 구현 코드 잠금