質問事項
Atcoderドワンゴからの挑戦状第四回予選C問題を下をコードで解いたのですが、一部のテストケースでWAになってしまいました。方針としてはこの問題の解説に従ったのですが、私の実装面で不備があるのか、または分割数やdpテーブルの定義に不備があるのかわかりません。どなたか教えていただけますでしょうか。
該当のソースコード
C++
1//#define _GLIBCXX _DEBUG 2#include <bits/stdc++.h> 3using namespace std; 4typedef long long ll; 5 6const int INF = INT_MAX; 7const int MOD = 1e9 + 7; 8vector<vector<ll>> P(1001, vector<ll>(1001,0)); 9ll solve(vector<int> &kill, vector<int> &death){ 10 deque<pair<int, int>> cnt; // cnt...キル数で分けたグループの集合 11 cnt.push_back({kill[0], 1}); //cnt.first キル数 cnt.second同じキル数の人数 12 for(ll i = 1; i < kill.size(); ++i){ 13 if(cnt.back().first == kill[i]) cnt.back().second++; 14 else cnt.push_back({kill[i], 1}); 15 } 16 int toll = 0; 17 for(auto i : death){ 18 toll += i; 19 } 20 int n = cnt.size(); 21 vector<vector<ll>> dp(n + 1, vector<ll>(toll + 1, 0)); // dp[group][d]:= group番目までで、デス数がdである組み合わせ数 22 dp[0][0] = 1; 23 for(int group = 0; group < n; ++group){ 24 for(int d = 0; d <= toll; ++d){ 25 for(int j = 0; j < toll - d + 1; ++j){ 26 dp[group + 1][d + j] += (dp[group][d] * P[cnt[group].second][j]); 27 dp[group + 1][d + j] %= MOD; 28 } 29 } 30 } 31 return dp[n][toll]; 32} 33int main(){ 34 ios::sync_with_stdio(false); 35 cin.tie(0); 36 int N, M; cin >> N >> M; 37 vector<int> A(N), B(M); 38 for(int i = 0; i < N; ++i) cin >> A[i]; 39 for(int i = 0; i < M; ++i) cin >> B[i]; 40 41 P[0][0] = 1; 42 for(int i = 1; i <= 1000; ++i ){ 43 for(int j = 0; j <= 1000; ++j){ 44 P[i][j] = P[i - 1][j]; 45 if(j >= i) P[i][j] += P[i][j - i]; //P[i][j]:= jをi個以下に分割する方法の総数 46 } 47 } 48 ll a = solve(A, B); 49 ll b = solve(B, A); 50 ll ans = a * b; 51 ans %= MOD; 52 cout << ans << endl; 53} 54

回答1件
あなたの回答
tips
プレビュー
下記のような回答は推奨されていません。
このような回答には修正を依頼しましょう。
また依頼した内容が修正された場合は、修正依頼を取り消すようにしましょう。
2022/09/26 13:21 編集
2022/09/26 13:21 編集
2022/09/26 14:33
2022/09/27 05:48
2022/09/27 05:51
2022/09/27 09:49 編集
2022/09/27 16:30 編集